枚举含p个元素的集合的子集，求出该子集和给定的若干个集合的交集，如果得到的这些交集都不相同，则该子集符合条件。题目要求求出符合条件的子集中最少含有多少个元素。
以下是我的代码：
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxp(17);
const int kMaxn(107);
bool cmp(const bitset<kMaxp> &a,const bitset<kMaxp> &b)
{
return (a.to_ulong()<b.to_ulong());
}
int p,n,ans;
bitset<kMaxp> r[kMaxn];
bitset<kMaxp> used,t[kMaxn];
bool OK()
{
for(int i=1;i<n;i++)
if(t[i]==t[i+1])
return false;
return true;
}
void dfs(int depth)
{
if(depth>p)
{
for(int i=1;i<=n;i++)
t[i]=r[i];
for(int i=1;i<=n;i++)
t[i]=t[i]&used;
sort(t+1,t+n+1,cmp);
if(OK())
ans=min(ans,(int)used.count());
return;
}
dfs(depth+1);
used[depth]=1;
dfs(depth+1);
used[depth]=0;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&p,&n);
for(int i=1;i<=n;i++)
r[i].reset();
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
{
int t;
scanf("%d",&t);
r[i][j]=t;
}
ans=315;
used.reset();
dfs(1);
printf("%d\n",ans);
}
return 0;
}
posted on 2011-04-15 17:29
lee1r 阅读(508)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索