题目描述
blablabla
样例
#include<iostream>
#include<vector>
#include<algorithm>
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(auto row :col[c]) i&=~row;
}
return res;
}
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[c].size()<col[t].size()) t=c;
}
for(auto row : col[t])
if(dfs(depth-1,state|row)) 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);
}
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)==false){
depth++;
}
if(depth>m) cout<<-1<<endl;
else cout<<depth<<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla