產生冠軍
Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11549????Accepted Submission(s): 5360
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
杭電計算機學科評估??
Author
qianneng
?
Source
迎接新學期——超級Easy版熱身賽
?
Recommend
lcy???|???We have carefully selected several similar problems for you:??2093?1811?2086?2647?2090?
RE: 據說一場沒輸過的就是贏家。
1 #include <map> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 map<string, int> acc; 7 int vis[1010], pic[1010][1010], indegree[1010]; 8 bool flag; 9 int n, k, top; 10 void Deal() 11 { 12 memset(vis, 0, sizeof(vis)); 13 memset(pic, 0, sizeof(pic)); 14 memset(indegree, 0, sizeof(indegree)); 15 acc.clear(); string a, b; k = 0; 16 for(int i = 0; i < n; i++) 17 { 18 cin >> a >> b; 19 if(!acc[a]) acc[a] = ++k; 20 if(!acc[b]) acc[b] = ++k; 21 if(pic[acc[a]][acc[b]] == 0) 22 { 23 pic[acc[a]][acc[b]] = 1; 24 indegree[acc[b]]++; 25 } 26 } 27 int total = 0; 28 for(int i = 1; i <= k; i++) 29 if(!indegree[i]) 30 total++; 31 if(total != 1) 32 flag = false; 33 } 34 void Tsort() 35 { 36 top = 0; int i; 37 while(top < k) 38 { 39 for(i = 1; i <= k; i++) 40 if(!vis[i] && !indegree[i]) 41 break; 42 vis[i] = 1; 43 top++; 44 for(int j = 1; j <= k; j++) 45 if(pic[i][j]) 46 indegree[j]--; 47 } 48 } 49 50 /*void Tsort(){ //WA: 不能保證沒輸過的只有一個人。 51 int m; 52 for(int j = 0; j < k; j++){ 53 m = -1; 54 for(int i = 1; i <= k; i++) 55 if(!indegree[i]){ 56 m = i; 57 break; 58 } 59 if(m == -1){ 60 flag = false; 61 break; 62 } 63 indegree[m]--; 64 for(int i = 1; i <= k; i++){ 65 if(pic[m][i]) 66 indegree[i]--; 67 } 68 } 69 } */ 70 71 int main() 72 { 73 while(~scanf("%d", &n), n) 74 { 75 flag = true; 76 Deal(); 77 Tsort(); 78 if(top < k) //好像是判環。 79 flag = false; 80 if(flag) 81 printf("Yes\n"); 82 else 83 printf("No\n"); 84 } 85 return 0; 86 }
?