产生冠军
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7509 Accepted Submission(s): 3558
Problem Description
有一群人,打乒乓球比赛,两两捉对撕杀,每两个人之间最多打一场比赛。
球赛的规则如下:
如果A打败了B,B又打败了C,而A与C之间没有进行过比赛,那么就认定,A一定能打败C。
如果A打败了B,B又打败了C,而且,C又打败了A,那么A、B、C三者都不可能成为冠军。
根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。
球赛的规则如下:
如果A打败了B,B又打败了C,而A与C之间没有进行过比赛,那么就认定,A一定能打败C。
如果A打败了B,B又打败了C,而且,C又打败了A,那么A、B、C三者都不可能成为冠军。
根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。
Input
输入含有一些选手群,每群选手都以一个整数n(n<1000)开头,后跟n对选手的比赛结果,比赛结果以一对选手名字(中间隔一空格)表示,前者战胜后者。如果n为0,则表示输入结束。
Output
对于每个选手群,若你判断出产生了冠军,则在一行中输出“Yes”,否则在一行中输出“No”。
Sample Input
3 Alice Bob Smith John Alice Smith 5 a c c d d e b e a d 0
Sample Output
Yes No
分析
感觉这个题。。。哎呀
如果A->B,C->D,D->E,E->C(“->”表示“打败”),哇噻!冠军产生了,恭喜A先生。。@#¥%##@%#*%#%。。一片厮打
勉强呈上AC代码
#include<stdio.h> #include<string.h> char s[50],dic[2004][50]; int map[2004][2004]; int main() { int n,k,i,j,h,a,b,r; while(scanf("%d",&n),n) { bool ok=1; memset(dic,0,sizeof(dic)); memset(map,0,sizeof(map)); scanf("%s%s",dic[1],dic[2]); map[1][2]=1; map[0][2]++; k=3; for(i=1; i<n; i++) { scanf("%s",s); a=k; strcpy(dic[k++],s); r=k; for(j=1; j<r-1; j++) if(strcmp(s,dic[j])==0) { a=j; k--; } scanf("%s",s); b=k; strcpy(dic[k++],s); r=k; for(j=1; j<r-1; j++) if(strcmp(s,dic[j])==0) { b=j; k--; } if(!map[a][b]) { map[a][b]=1; map[0][b]++; } } k--; // for(i=1; i<=k; i++) // for(j=1; j<=k; j++) // for(h=1; h<=k; h++) // { // if(map[i][j]&&map[j][h]&&!map[i][h]) // map[i][h]=1; // } // for(i=1; i<=k; i++) // { // for(j=1; j<=k; j++) // if(map[i][j]&&map[j][i]) // { // ok=0; // printf("No\n"); // break; // } // if(!ok) break; // } // if(!ok) continue; int num=0; for(i=1;i<=k;i++) { if(!map[0][i]) num++; } if(num==1) printf("Yes\n"); else printf("No\n"); } return 0; }