题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1285
确定比赛名次
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18516 Accepted Submission(s): 7410
Problem 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
Author
SmallBeer(CML)
Source
分析:拓扑排序。即对有向无环图(DGA)进行排序。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int Map[505][505]; int num[505]; int used[505]; int head[50005]; int p; struct node { int next,v,u; }a[50050]; void add(int p1,int p2) { a[p].u = p1; a[p].v = p2; a[p].next = head[p1]; head[p1] = p++; } int main() { int n,m,p1,p2; while(~scanf("%d %d", &n, &m)) { memset(Map, 0, sizeof(Map)); memset(num, 0, sizeof(num)); memset(used, 0, sizeof(used)); memset(head,-1,sizeof(head)); p=0; for(int i=1; i<=m; i++) { scanf("%d %d", &p1, &p2); add(p1,p2);//邻接表存图。 num[p2]++; } int aa[505],k=0; while(k!=n)//没有完全确定排名 { for(int i=1; i<=n; i++) { if(num[i] == 0 && !used[i])//当i前的全都排序而且i没有被排序 { aa[k++] = i; break; } } used[aa[k-1]] = 1; int u = aa[k-1]; for(int i=head[u]; i!=-1; i=a[i].next) { int v = a[i].v; num[v]--;//由于u排好序,与u连接的点则应该减一。 } } for(int i = 0; i < k; i++) printf("%d%c", aa[i], i==k-1?' ':' '); } return 0; }
邻接矩阵T了好久,终于A了。原来有重边。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int Map[505][505]; int num[505],a[505]; int main() { int n,m,p1,p2; while(~scanf("%d %d", &n, &m)) { memset(Map, 0, sizeof(Map)); memset(num, 0, sizeof(num)); for(int i=1; i<=m; i++) { scanf("%d %d", &p1, &p2); if(Map[p1][p2]==0)//避免重边 { Map[p1][p2]=1; num[p2]++; } } int k=0; while(k!=n) { for(int i=1; i<=n; i++) { if(num[i] == 0 ) { num[i]--; a[k++] = i; for(int ii=1;ii<=n;ii++) { if(Map[i][ii]) { Map[i][ii]=0; num[ii]--; } } break; } } } for(int i = 0; i < k; i++) printf("%d%c", a[i], i==k-1?' ':' '); } return 0; }