首页 > 代码库 > HDU 4068 dfs枚举

HDU 4068 dfs枚举

2024-07-30 20:23:52   219人阅读

SanguoSHA

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 944    Accepted Submission(s): 520


Problem Description
Sanguosha has a singled version. Two players each select N heroes and start fighting. If a hero dies, the next follows. If one player‘s heroes are all dead, he loses.

There‘re restraints among heroes. For example, YuJi restricts Zhu Geliang, LuXun restricts DaQiao, ZhangJiao restricts MaChao, WeiYan restricts XiaoQiao. 
Today I play with friends. I know the heroes and the restraints.(If opponent‘s hero restraint my hero, my hero will be beaten, others my hero will beat opponent‘s hero)
Can you arrange my heroes‘ order,no matter what order of opponent‘s heroes, so that I can win the game?
 

 

Input
The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
The first line is N(3<=N<=6).
The second line has N names(shorter than 20 letter).
The following N lines each contains a restraints. Restraints are given as “k b1 b2 … bk”, which means the opponent‘s hero restricts my hero b1, b2 … bk. (0<=K<=N)
 

 

Output
For each case, first line output the number of case with "Yes" or "No". If Yes, output the order of your heroes separate by a space. If there are more than one order, please output the one with minimum lexicographic order.(as shown in the sample output)
 

 

Sample Input
2
3
ZhugeLiang HuangYueying ZhenJi
1 ZhugeLiang
2 HuangYueying ZhenJi
2 ZhugeLiang ZhenJi
4MaChao YanLiangWenChou YuJin XiaoQiao
2 MaChao XiaoQiao
2 YanLiangWenChou YuJin
1 XiaoQiao
0
 

 

Sample Output
Case 1: No
Case 2: Yes
MaChao YanLiangWenChou XiaoQiao YuJin
 
 
 
题目意思：
给出你手中的牌和敌人克你的牌，然后问你是否有一种出牌顺序，使得不管敌人怎么出你都会赢，若没有输出No,否则输出Yes和你出牌的顺序，若有多种情况，输出字典序最小的顺序。
 
 
思路：
牌数最多为6，为保证字典序最小，先按字典序对自己手中牌排序，那么就用dfs枚举自己手里牌的顺序，当确定住自己手中牌的顺序时，枚举敌人手中牌的顺序，若在你此时手中牌的顺序时，赢得情况为n!，那么就输出顺序就行了，两个dfs就搞定了。
 
 
代码：
  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <iostream>  5 #include <queue>  6 #include <vector>  7 #include <map>  8 using namespace std;  9  10 struct node{ 11     int id; 12     string s; 13 }a[10]; 14 map<string,int>ma; 15  16 string S[10]; 17 int n; 18 int visited1[10]; 19 int visited2[10]; 20 int cnt[10][10]; 21 int dep1[10]; 22 int dep[10]; 23 int f; 24 int kase; 25 int nn; 26 int maxh; 27  28 bool cmp(node a,node b){ 29     return a.s<b.s; 30 } 31  32 void dfs1(int k){ 33     int i, j; 34     if(f>=nn) return; 35     if(k>=n){ 36         int num1=n, num2=n; 37         i=j=0; 38         while(i<num1&&j<num2){ 39             if(cnt[dep1[j]][dep[i]]) i++; 40             else j++; 41         } 42         if(i<num1){ 43             f++; 44         } 45     //    maxh=max(maxh,f); 46         if(f>=nn){ 47             printf("Case %d: Yes\n",kase); 48             cout<<S[0]; 49             for(i=1;i<n;i++) cout<<" "<<S[i]; 50             cout<<endl; 51         } 52              53             return; 54          55     } 56     for(i=0;i<n;i++){ 57         if(!visited2[i]){ 58             visited2[i]=1; 59             dep1[k]=i; 60             dfs1(k+1); 61             visited2[i]=0; 62         } 63     } 64 } 65  66 void dfs(int kase,int k){ 67     int i; 68     if(f>=nn) return; 69     if(k>=n){ 70         f=0; 71         dfs1(0); 72         return; 73     } 74     for(i=0;i<n;i++){ 75         if(!visited1[i]){ 76             visited1[i]=1; 77             S[k]=a[i].s; 78             dep[k]=a[i].id; 79             dfs(kase,k+1); 80             visited1[i]=0; 81         } 82     } 83      84 } 85 main() 86 { 87     int t, i, j, k;kase=1; 88     cin>>t; 89     string str; 90     while(t--){ 91         k=0; 92         memset(cnt,0,sizeof(cnt)); 93         memset(visited1,0,sizeof(visited1)); 94         memset(visited2,0,sizeof(visited2)); 95         ma.clear(); 96         scanf("%d",&n); 97         nn=1; 98         for(i=1;i<=n;i++) nn*=i; 99         for(i=0;i<n;i++) {100             cin>>a[i].s;101             a[i].id=i;102             ma[a[i].s]=k++;103         }104         sort(a,a+n,cmp);105         j=0;106         for(i=0;i<n;i++){107             scanf("%d",&k);108             while(k--)109             {110                 cin>>str;111                 cnt[j][ma[str]]=1;112             }113             j++;114         }115         f=0;116         maxh=-1;117         dfs(kase,0);118         if(f<nn){119             printf("Case %d: No\n",kase);120         }121     //    printf("%d\n",maxh);122         kase++;123     }124 }

 

HDU 4068 dfs枚举


联系
我们