23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // (Minimum) Set Cover
23dfcca431 2011-02-23        kinaba: //   NP-complete
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Consider using SetCoverEasy, when mask is downward closed.
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
23dfcca431 2011-02-23        kinaba: //   - SRM345 Div1 LV3
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: LL next_combination(LL p)
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	LL lsb = p & -p;
23dfcca431 2011-02-23        kinaba: 	LL rem = p + lsb;
23dfcca431 2011-02-23        kinaba: 	LL rit = rem & ~p;
23dfcca431 2011-02-23        kinaba: 	return rem|(((rit/lsb)>>1)-1);
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: // Is it possible to cover the goal by at most k elements from mask?
23dfcca431 2011-02-23        kinaba: // Assumption:  goal \subseteq \bigcup mask
23dfcca431 2011-02-23        kinaba: bool canCover( LL goal, set<LL>& mask, int k )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	// optimizer
23dfcca431 2011-02-23        kinaba: 	for(bool update=true; update; ) {
23dfcca431 2011-02-23        kinaba: 		update = false;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		// if *it \subseteq *jt for some jt, then we NEVER use it
23dfcca431 2011-02-23        kinaba: 		// if *it is the only mask covering some city, we ALWAYS use it
23dfcca431 2011-02-23        kinaba: 		for(set<LL>::iterator it=mask.begin(); it!=mask.end(); ) {
23dfcca431 2011-02-23        kinaba: 			bool isSubset = false;
23dfcca431 2011-02-23        kinaba: 			LL   onlyByMe = *it & goal;
23dfcca431 2011-02-23        kinaba: 			for(set<LL>::iterator jt=mask.begin(); jt!=mask.end(); ++jt)
23dfcca431 2011-02-23        kinaba: 				if( it!=jt ) {
23dfcca431 2011-02-23        kinaba: 					onlyByMe &= ~*jt;
23dfcca431 2011-02-23        kinaba: 					isSubset |= (*it & *jt & goal) == (*it & goal);
23dfcca431 2011-02-23        kinaba: 				}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 			update |= isSubset | !!onlyByMe;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 			if( isSubset )
23dfcca431 2011-02-23        kinaba: 				mask.erase(it++);
23dfcca431 2011-02-23        kinaba: 			else if( onlyByMe ) {
23dfcca431 2011-02-23        kinaba: 				if( --k < 0 )
23dfcca431 2011-02-23        kinaba: 					return false;
23dfcca431 2011-02-23        kinaba: 				goal &= ~*it;
23dfcca431 2011-02-23        kinaba: 				mask.erase(it++);
23dfcca431 2011-02-23        kinaba: 			}
23dfcca431 2011-02-23        kinaba: 			else
23dfcca431 2011-02-23        kinaba: 				++it;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		if( mask.size()<=k || goal==0 )
23dfcca431 2011-02-23        kinaba: 			return true;
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	// exhaustive search
23dfcca431 2011-02-23        kinaba: 	vector<LL> ms(mask.begin(), mask.end());
23dfcca431 2011-02-23        kinaba: 	for(LL i=(1LL<<k)-1; i<(1LL<<ms.size()); i=next_combination(i))
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		LL gg = goal;
23dfcca431 2011-02-23        kinaba: 		for(LL j=0; (1LL<<j)<=i; ++j)
23dfcca431 2011-02-23        kinaba: 			if( i & (1<<j) )
23dfcca431 2011-02-23        kinaba: 				gg &= ~ms[j];
23dfcca431 2011-02-23        kinaba: 		if( gg == 0 )
23dfcca431 2011-02-23        kinaba: 			return true;
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 	return false;
23dfcca431 2011-02-23        kinaba: }