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