心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
枚举含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 阅读(519) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:搜索

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理