HDU 1285

B - 确定比赛名次

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3

1 2

2 3

4 3

Sample Output

1 2 4 3

我知道是很简单一道题，但是自己做起来还是很曲折，百度了一下使用拓补排序，然后就开始学拓补，但是写出来之后没有办法处理输出时编号小的在前面这个问题。想了一下还是不知道怎么解决，就换了一种思路，结果就一直交，一直错。最后也没写好，找了一份别人的代码理解了一下。先这样吧，我一定改好了交上。

 1 //这是错误的代码好歹我写了好长时间呢，留着好改
 2 #include<stdio.h>
 3 #include<string.h>
 4 const int N = 505;  
 5 
 6 bool g[N][N];  
 7 int n, m,t,max = 1; 
 8 int main()
 9 {  int c[N];
10     int i, x, y,j;  
11     while(scanf("%d%d", &n, &m) != EOF) 
12     {  
13         memset(g, false, sizeof(g)); 
14         memset(c,-1,sizeof(c));
15   
16         for(i = 0; i < m; i++)         
17         {  
18             scanf("%d%d", &x, &y);  
19             if(g[x][y] == false)  
20             { 
21                 g[x][y] = true;
22                 if(c[x] == -1)c[x] = 0;
23                 if(c[y] == -1)c[y] = 0;
24                 if(c[x] < c[y] +1)c[x] = c[y] +1;//c中存的是第i个队能打败多少队
25                 
26                 if(t < c[x])t = c[x];//t是最多能打败的队数
27             }         
28         }  
29         j = 0;//下面就是输出啦，因为要按字典序输出么就很费事
30         while(t > 0)
31         {
32             for(i = 1;i <= n;i++)
33             {
34                 if(c[i]== -1&&i <= max){printf("%d ",i);j++;if(max < i)max = i;c[i] = 10000;}
35                 if(c[i] == t){printf("%d ",i);j++;if(max < i)max = i;c[i] = 10000;}
36             }
37             t--;
38         }
39         for(i = 1;i <= n && (n-j) > 1;i++)
40             {
41                 if(c[i]== -1&&i <= max){printf("%d ",i);j++;if(max < i)max = i;c[i] = 10000;}
42                 if(c[i] == t){printf("%d ",i);j++;if(max < i)max = i;c[i] = 10000;}
43             }
44         for(i = 1;i <= n;i++)
45             {
46                 if(c[i]== -1){printf("%d
",i);}
47                 else if(c[i] == t){printf("%d
",i);}
48             }
49     }  
50     return 0;
51 }

View Code

下面是大神的代码

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 int array[501][501];
 8 int res[501];
 9 
10 void Tuopu(int n)
11 {
12     int d[501], j;
13 
14     for (int i = 0; i < n; i++)
15     {
16         for (d[i] = j = 0; j < n; j++)
17         {
18             d[i] += array[j][i];//d好像存的是有几个参赛者比i强
19         }
20     }
21 
22     for (int i = 0; i < n; i++)
23     {
24         int p;
25 
26         for (int j = 0; j < n; j++)
27         {
28             if (d[j] == 0)//找到目前最大的
29             {
30                 d[j] = -1;//标记一下
31                 res[i] = j;//放入结果中
32                 p = j;//p记录上一个
33                 break;
34             }
35         }
36         for (int j = 0; j < n; j++)
37         {
38             d[j] -= array[p][j];//所有被p打败的都少了一个对手
39         }
40     }
41 }
42 
43 int main()
44 {
45     int n, m;
46 
47     while(cin >> n >> m)
48     {
49         if (n == 0 && m == 0) break;
50         memset(array, 0, sizeof(array));
51         for (int i = 0; i < m; i++)
52         {
53             int x, y;
54             cin >> x >> y;
55             array[x - 1][y - 1] = 1;
56         }
57         Tuopu(n);
58         for (int i = 0; i < n; i++)
59         {
60             cout << res[i] + 1;
61             if (i != n - 1)
62             {
63                 cout << ' ';
64             }
65         }
66         cout << endl;
67     }
68     return 0;
69 }

View Code

他并没有可以按字典序输出但是结果还是字典序的，我想可能是因为在遍历找出结果的时候一直是顺序查找的，而且没有参加比赛的对的d就是0 可以直接被顺序遍历，而且找到一个就break了。

我照着白书打了一个用拓补排序只输出一个结果的代码（不一定是字典序）也要贴上来。

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int N = 505;  
 4 int c[N], topo[N],ad[N];  
 5 bool g[N][N];  
 6 int n, m,t;  
 7 bool dfs (int u)
 8 {
 9     int v,i;
10     c[u] = -1;
11     for(v = 1;v <= n;v++)
12     {
13         if(g[u][v])
14         {
15             if(c[v] < 0)return false;
16             else if(!c[v] && !dfs(v))return false;
17         }
18     }
19     c[u] = 1;
20     topo[--t] = u;
21     return true;
22 }
23 bool Topo()
24 {
25     int u;
26     t = n;
27     memset(c,0,sizeof(c));
28     for(u = 1;u <= n;u++)if(!c[u])
29         if(!dfs(u))return false;
30     return true;
31 }
32 int main()
33 {
34     int i, x, y;  
35     while(scanf("%d%d", &n, &m) != EOF) 
36     {  
37         memset(g, false, sizeof(g)); 
38         memset(topo, 0, sizeof(topo));  
39         for(i = 0; i < m; i++)         
40         {  
41             scanf("%d%d", &x, &y);  
42             if(g[x][y] == false)  
43             { 
44                 g[x][y] = true;   
45             }         
46         }  
47         if(Topo())
48             for(i = 0;i < n;i++ )printf("%d ",topo[i]);
49     }  
50     return 0;
51 }

View Code

具体过程我写书上了，有时间在整理一下。