Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4148????Accepted Submission(s): 1547
?
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 Input4 3 1 2 2 3 4 3
?
Sample Output1 2 4 3? ??????? 最简单的拓扑排序,数目很小,直接用矩阵。后来做的题发现有很多都不能用矩阵表示,要用邻接表或者链表来表示,主要是先找deg[i]为0的,他就排在前面,然后以他为起点,跟他连接的点的deg[]--,如此下去,排名是按分数优先,分数相同的按字典顺序排,先贴这道题的代码。 链接:http://acm.hdu.edu.cn/showproblem.php?pid=1285 代码:
#include <iostream> #include <stdio.h> #include <memory.h> #include <vector> using namespace std; const int N = 505; int degree[N], res[N]; bool map[N][N]; vector<int> a[N]; int n, m; void Topo() { int i, j, p; for(i = 1; i <= n; i++) { p = -1; for(j = 1; j <= n; j++) { if(degree[j] == 0) { degree[j]--; res[i] = p = j; break; } } for(j = 1; j <= n; j++) { if(map[p][j] == true) { map[p][j] = false; degree[j]--; } } } } void output() { int i; printf("%d", res[1]); for(i = 2; i <= n; i++) { printf(" %d", res[i]); } printf("\n"); } int main() { int i, x, y; while(scanf("%d %d", &n, &m) != EOF) { memset(map, false, sizeof(map)); memset(degree, 0, sizeof(degree)); memset(res, 0, sizeof(res)); for(i = 1; i <= n; i++) a[i].clear(); for(i = 1; i <= m; i++) { scanf("%d %d", &x, &y); if(map[x][y] == false) { map[x][y] = true; degree[y]++; } } Topo(); output(); } return 0; }?