AcWing 1243. 位运算+剪枝
原题链接
中等
作者:
W.W
,
2021-03-29 22:17:40
,
所有人可见
,
阅读 699
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 110, M = 1<<20;
int n, m, k;
vector<int> col[N];
int log2[M];
int lowbit(int x)
{
return x & -x;
}
int h(int state)
{
int res = 0;
for(int i = (1<<m)-1-state; i; i-=lowbit(i))
{
int c = log2[lowbit(i)];
res ++;
for(int j=0; j<col[c].size(); j++) {
i &= ~col[c][j];
}
}
return res;
}
bool dfs(int depth, int state)
{
if(depth == 0 )
{
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(int i =0; i<col[t].size(); i++)
{
if(dfs(depth-1, state | col[t][i]))
{
return true;
}
}
return false;
}
int main()
{
cin>>n>>m>>k;
for(int i=0; i<m; i++)
log2[1<<i] = i;
for(int i=0; i<n; i++)
{
int state = 0;
for(int j =0; j<k; j++)
{
int c;
cin>>c;
state |= 1<< (c-1);
}
for(int j = 0; j<m; j++)
{
if((state >> j) & 1)
{
col[j].push_back(state);
}
}
}
int depth = 1;
while(depth<=m && !dfs(depth,0))
{
depth++;
}
if(depth>m) depth = -1;
cout<<depth<<endl;
return 0;
}
LZ dfs里忘了加h了。。。