AcWing 1243. 糖果
原题链接
中等
作者:
geats兔
,
2024-04-10 17:55:36
,
所有人可见
,
阅读 2
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N =110,M=1<<21;
vector<int> col[N];
int log2[M];
int m,n,k;
int lowbit(int x) // 返回末尾的1
{
return x & -x;
}
int h(int state)
{
int count=0;
for(int i=(1<<m)-1-state;i;i-=lowbit(i))
{
int c=log2[lowbit(i)];
count++;
for(auto&t:col[c])
i&=~t;
}
return count;
}
bool dfs(int depth,int state)
{
if(!depth||h(state)>depth) return state==(1<<m)-1;
int t=-1;
for(int i=(1<<m)-1-state;i;i-=lowbit(i))
{
int c=log2[lowbit(i)];
if(t==-1||col[t].size()>col[c].size())
t=c;
}
for(auto& t:col[t])
{
if(dfs(depth-1,state|t)) return true;
}
return false;
}
int main()
{
cin>>n>>m>>k;
for (int i = 0; i < m; i ++ ) log2[1 << i] = i;
for (int i = 1; i <=n; i ++ )
{
int state=0;
for (int j =1; j <=k; j ++ )
{
int t;
cin>>t;
state|=1<<t-1;
}
for (int j = 0; j < m; j ++)
{
if(state>>j&1)
col[j].push_back(state);
}
}
for (int i = 0; i < m; i ++ )
{
sort(col[i].begin(), col[i].end());
col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end());
}
int depth=0;
while(depth<=m&&!dfs(depth,0)) depth++;
if(depth>m) cout<<-1<<endl;
else cout<<depth<<endl;
return 0;
}