hdu 5506 GT and set（dfs爆搜）

缺乏、安全感 2022-03-30 04:48 85阅读 0赞

Problem Description

You are given N sets.Thei−th set hasAi numbers.  
You should divide the sets intoL parts.  
And each part should have at least one number in common.  
If there is at least one solution,printYES,otherwise printNO.

Input

In the first line there is the testcase T (T≤20)  
For each teatcase:  
In the first line there are two numbersN andL.  
In the nextN lines,each line describe a set.  
The first number isAi,and then there areAi distict numbers stand for the elements int the set.  
The numbers in the set are all positive numbers and they're all not bigger than300.  
1≤N≤30，1≤L≤5，1≤Ai≤10，1≤L≤N  
You'd better print the enter in the last line when you hack others.  
You'd better not print space in the last of each line when you hack others.

Output

For each test print YES orNO

Sample Input

2 2 1 1 1 1 2 3 2 3 1 2 3 3 4 5 6 3 2 5 6

Sample Output

NO YES

*Hint*

For the second test,there are three sets:\{1,2,3\},\{4,5,6\},\{2,5,6\} You are asked to divide into two parts. One possible solution is to put the second and the third sets into the same part,and put the first in the other part. The second part and the third part have same number 6. Another solution is to put the first and the third sets into the same part,and put the second in the other part.

**题意:**

**有n个集合,问你能否在L次内把所有集合都删去,如果两个或者更多集合内含有一个相同的数,则这些集合可以同时删除**

**每个集合中的元素小于10,L<=5,n<=30**

**分析:**

**由于数据范围都比较小,很容易想到搜索**

**很容易想到可以枚举当前集合应该删除哪个数,如果下一个集合中已经出现过了这个数,则跳过下一个集合,可以选择的删除的数不超过5个**

**每个集合中最多有10个数能被选择,所以时间复杂度也就为10^5\*n,乘以n是因为要判断需不需要从当前这个集合中删除一个数**

**首先贴上第一个代码，这个代码在oj上能AC，但是题目给出的样例中的第一个样例却过不来。和下面贴出的第二个样例写得差不多，但就是样例有一个过不了，不懂什么原因。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #pragma comment(linker, "/STACK:1024000000,1024000000")
     2 #include<iostream>
     3 #include<cstdio>
     4 #include<cstring>
     5 #include<cmath>
     6 #include<math.h>
     7 #include<algorithm>
     8 #include<queue>
     9 #include<set>
    10 #include<bitset>
    11 #include<map>
    12 #include<vector>
    13 #include<stdlib.h>
    14 using namespace std;
    15 #define ll long long
    16 #define eps 1e-10
    17 #define MOD 1000000007
    18 #define N 36
    19 #define M 306
    20 #define inf 1e12
    21 int n,L;
    22 vector<int> g[N];
    23 int s[N];
    24 int vis[M];
    25 int flag;
    26 bool judge(int num){
    27     for(int i=0;i<s[num];i++){
    28         int val=g[num][i];
    29         if(vis[val]){
    30             return true;
    31         }
    32     }
    33     return false;
    34 }
    35 void dfs(int num,int d){
    36     if(num>=n){
    37         flag=1;
    38         return;
    39     }
    40     if(judge(num)){
    41         dfs(num+1,d);
    42     }
    43     if(flag){
    44         return;
    45     }
    46     
    47     if(d>L){
    48         return;
    49     }
    50     
    51     for(int i=0;i<s[num];i++){
    52         int val=g[num][i];
    53         vis[val]=1;
    54         dfs(num+1,d+1);
    55         if(flag){
    56             return;
    57         }
    58         vis[val]=0;
    59     }
    60 }
    61 int main()
    62 {
    63     int t;
    64     scanf("%d",&t);
    65     while(t--){
    66         scanf("%d%d",&n,&L);
    67         for(int i=0;i<=n;i++){
    68             g[i].clear();
    69         }
    70         for(int i=0;i<n;i++){
    71             scanf("%d",&s[i]);
    72             for(int j=0;j<s[i];j++){
    73                 int c;
    74                 scanf("%d",&c);
    75                 g[i].push_back(c);
    76             }
    77         }
    78         memset(vis,0,sizeof(vis));
    79         flag=0;
    80         dfs(0,0);
    81         if(flag==1){
    82             printf("YES\n");
    83         }else{
    84             printf("NO\n");
    85         }
    86         
    87     }
    88     return 0;
    89 }

**第二个代码，正确。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #pragma comment(linker, "/STACK:1024000000,1024000000")
     2 #include<iostream>
     3 #include<cstdio>
     4 #include<cstring>
     5 #include<cmath>
     6 #include<math.h>
     7 #include<algorithm>
     8 #include<queue>
     9 #include<set>
    10 #include<bitset>
    11 #include<map>
    12 #include<vector>
    13 #include<stdlib.h>
    14 using namespace std;
    15 #define ll long long
    16 #define eps 1e-10
    17 #define MOD 1000000007
    18 #define N 36
    19 #define M 306
    20 #define inf 1e12
    21 int n,L;
    22 vector<int> g[N];
    23 int s[N];
    24 int vis[M];
    25 int flag;
    26 bool judge(int num){
    27     for(int i=0;i<s[num];i++){
    28         int val=g[num][i];
    29         if(vis[val]){
    30             return true;
    31         }
    32     }
    33     return false;
    34 }
    35 bool dfs(int num,int d){
    36     
    37     if(num>=n){
    38         //flag=1;
    39         return true;
    40     }
    41     if(judge(num)){
    42         return dfs(num+1,d);
    43     }
    44     //if(flag) return;
    45     if(d>=L) return false;
    46     for(int i=0;i<s[num];i++){
    47         int val=g[num][i];
    48         vis[val]=1;
    49         if(dfs(num+1,d+1)) return true;
    50         //if(flag){
    51         //    return;
    52     //    }
    53         vis[val]=0;
    54     }
    55     return false;
    56 }
    57 int main()
    58 {
    59     int t;
    60     scanf("%d",&t);
    61     while(t--){
    62         scanf("%d%d",&n,&L);
    63         for(int i=0;i<=n;i++){
    64             g[i].clear();
    65         }
    66         for(int i=0;i<n;i++){
    67             scanf("%d",&s[i]);
    68             for(int j=0;j<s[i];j++){
    69                 int c;
    70                 scanf("%d",&c);
    71                 g[i].push_back(c);
    72             }
    73         }
    74         memset(vis,0,sizeof(vis));
    75         /*flag=0;
    76         dfs(0,0);
    77         if(flag==1){
    78             printf("YES\n");
    79         }else{
    80             printf("NO\n");
    81         }
    82         */
    83         printf("%s\n", dfs(0, 0) ? "YES" : "NO");
    84         
    85     }
    86     return 0;
    87 }

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220330/060f727e02eb4ee4bb17996d921bcd0b.png