hdu 1285 确定比赛名次拓扑排序

浏览数：29 / 时间：2015年06月08日

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1285

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

题意描述：如原题所示。

算法分析：拓扑排序，然后输出上要求合理答案中字典序最小的一个排列。我挫比了，首先想到的是优先队列来处理。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #define inf 0x7fffffff
 9 using namespace std;
10 const int maxn=500+10;
11 
12 int n,m;
13 struct node
14 {
15     int u;
16     friend bool operator < (node a,node b)
17     {
18         return a.u > b.u;
19     }
20 }cur,tail;
21 int graph[maxn][maxn],in[maxn];
22 int an[maxn],cnt;
23 
24 void topsort()
25 {
26     cnt=0;
27     priority_queue<node> Q;
28     for (int i=1 ;i<=n ;i++) if (in[i]==0)
29     {
30         cur.u=i;
31         Q.push(cur);
32     }
33     while (!Q.empty())
34     {
35         cur=Q.top() ;Q.pop() ;
36         int u=cur.u;
37         an[cnt++]=u;
38         for (int i=1 ;i<=n ;i++)
39         {
40             if (graph[u][i] && i!=u)
41             {
42                 in[i]--;
43                 if (in[i]==0)
44                 {
45                     cur.u=i;
46                     Q.push(cur);
47                 }
48             }
49         }
50     }
51     int flag=0;
52     for (int i=0 ;i<cnt ;i++)
53     {
54         if (flag) printf(" ");
55         flag=1;
56         printf("%d",an[i]);
57     }
58     printf("\n");
59 }
60 
61 int main()
62 {
63     while (scanf("%d%d",&n,&m)!=EOF)
64     {
65         int a,b;
66         memset(graph,0,sizeof(graph));
67         memset(in,0,sizeof(in));
68         for (int i=1 ;i<=m ;i++)
69         {
70             scanf("%d%d",&a,&b);
71             if (graph[a][b]==0) in[b] ++ ;
72             graph[a][b]=1;
73         }
74         topsort();
75     }
76     return 0;
77 }