GT and set

Accepts: 35

Submissions: 194

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

有NN个集合，每个集合中有A_iAi个数。

你要将这NN个集合划成LL个部分，使得每个部分的集合至少有一个共有的数。

如果至少有一个解输出YESYES，否则输出NONO

输入描述

第一行一个数T表示数据组数。（TT\leq≤2020）

对于每一组数据：

第一行两个数NN和LL。

接下来NN行每行描述一个集合：

第一个数A_iAi表示该集合的大小，之后xx个互不相同的整数表示该集合的元素。

集合里的数字都是正整数且不大于300300.

1\leq1≤NN\leq30≤30，1\leq1≤L\leq5L≤5，1\leq1≤A_iAi\leq10≤10，1 \leq L \leq N1≤L≤N

hack时建议输出最后一行的行末回车;每一行的结尾不要输出空格。

输出描述

对于每组数据输出一行YESYES或NONO

输入样例

输出样例

NO

YES

Hint

对于第二个样例，有三个集合{1 2 3}，{4 5 6}，{2 5 6} 你要划成两个部分。

有一种方案是把第二个和第三个集合划成一个部分，第一个在另一个部分。有一种方案是把第二个和第三个集合划成一个部分，第一个在另一个部分。 第二个和第三个集合的数字有一个交集{6}，所以合法。

还有一种划分方案就是把第一个和第三个集合划成一个部分，第二个在另一个部分。

///

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#include<bitset>

#include<set>

#include<vector>

using namespace std ;

typedef unsigned long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define meminf(a) memset(a,127,sizeof(a));

#define memfy(a)  memset(a,-1,sizeof(a));

#define TS printf("111111\n");

#define FOR(i,a,b) for( int i=a;i<=b;i++)

#define FORJ(i,a,b) for(int i=a;i>=b;i--)

#define inf 100000000

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************************

#define maxn 33

bool flag,vis[maxn];

int num[maxn],n,A,L;

bitset<> S[maxn],tmp,temp,aa[maxn];

void dfs(int x)

{

      if(x==n+)

      {

          flag=;

          for(int i=;i<=L;i++)

          {

              if(!num[i])flag=;

          }

          return ;

      }

        if(flag)return ;

      for(int i=;i<=L;i++){

        temp=aa[i];

          tmp=aa[i]&S[x];

          if(tmp.count()!=)

          {

              aa[i]=tmp;

              num[i]++;

              dfs(x+);

              num[i]--;

              aa[i]=temp;

          }

      }

}

int main()

{

    int T=read();

    while(T--)

    {

        scanf("%d%d",&n,&L);

        mem(vis);mem(num);

        FOR(i,,){

            S[i].reset();aa[i].set();

        }

        FOR(i,,n){

            scanf("%d",&A);

            FOR(j,,A){

                int x=read();

                S[i].set(x);

            }

        }

    //    for(int i=1;i<=6;i++)cout<<S[3][i];

        flag=;

        dfs();

        if(flag){

            cout<<"YES"<<endl;

        }

        else{

            cout<<"NO"<<endl;

        }

    }

    return ;

}

代码

巴特西

BestCoder Round #60.1003.GT and set/HDU5506 dfs

GT and set

最新文章

热门文章