Artifact d2930c13625ebb9212dca232b7282a48d8458bb6
//-------------------------------------------------------------
// (Minimum) Set Cover
// NP-complete
//
// Assumption: "mask" must be downward closerd,
// i.e., X subset Y & Y in mask => X in mask
//
// Verified by
// - Google Code Jam 09 Round2 C
// (The "Only" part never tested, in the test cases of
// the problem, that optimization had never used.
// Be careful to use that; to be on the safer side,
// consider using the <true,false> mode.)
//-------------------------------------------------------------
int minCover_exhaustive( int goal, const set<int>& mask )
{
typedef int STATE;
vector<STATE> Q( 1, 0 );
set<STATE> visited;
for(int step=0; step<=mask.size(); ++step)
{
vector<STATE> Q2;
for(int i=0; i<Q.size(); ++i)
{
STATE s = Q[i];
if( s == goal )
return step;
for(set<int>::const_iterator it=mask.begin(); it!=mask.end(); ++it)
if( !visited.count( s|*it ) )
{
visited.insert( s|*it );
Q2.push_back( s|*it );
}
}
Q.swap(Q2);
}
return -1;
}
template<bool Subs, bool Only>
int minCover( int goal, set<int> mask )
{
if( Subs )
for(set<int>::iterator it=mask.begin(); it!=mask.end(); )
{
bool needed = true;
for(int m=1; m<=goal; m<<=1)
if( (goal&m) && !(*it&m) && mask.count(*it|m))
{needed = false; break;}
if( needed )
++it;
else
mask.erase(it++);
}
if( Only )
for(set<int>::iterator it=mask.begin(); it!=mask.end(); )
{
int onlyByMe = goal & *it;
for(set<int>::iterator jt=mask.begin(); jt!=mask.end(); ++jt)
onlyByMe &= ~*jt;
if( !onlyByMe )
++it;
else
mask.erase(it++), goal &= ~onlyByMe;
}
return minCover_exhaustive(goal, mask);
}