非常坑的一道题，最后快要绕晕了。。
题意：有N个球，重量分别是1~N，给着n个球贴上标签。输入n，m代表n个球和m条边(a b)，代表 标签为a的要比标签为b的轻。最后输出标签1~N对应的重量（注意是重量，而不是轻重关系），还有要注意“ you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... ”,意思是标签小的要尽可能贴在重量小的球上。
思路：因为标签小的要尽可能贴在重量小的球上，所以拓扑排序时要使标签小的尽可能的靠前。所以只是传统的拓扑排序每次取优先队列中入度为0并且数最小的不对的。因为即使该点最小，它后面连着的点未必是最小的。
例如上图，若先取入度为0且最小的话，是先取出3，而我们的目的是让标号小的尽量靠前，即应该让1尽量靠前，这与先取出3相违背，这时应该先取出6才能使1尽量靠前。对于2,8，2肯定先出队列。归纳起来便是对于若干平行的路径，小的头部不一定排在前面（如3），但大的尾部一定排在后面（如8）.
1. 把所有出度为 0 的节点放进优先队列 PQ 2. WHILE： PQ 不是空队列 3. 从 PQ 中取出编号最大的元素 a，把 a 添加到答案的头部。 4. FOR：所有指向 a 的边 b → a 5. 把 b 的出度减 1。如果 b 的出度变为 0，则把 b 放进优先队列 PQ。
#include#include #include #include using namespace std; int n,m; int out[210]; int topo[210]; int map[210][210]; priority_queue < int, vector ,less > que; int toposort() { while(!que.empty()) que.pop(); int cnt = 1; memset(topo,0,sizeof(topo)); for(int i = 1; i <= n; i++) if(out[i] == 0) que.push(i); while(!que.empty()) { int u = que.top(); //每次取出队列中最大的 que.pop(); topo[cnt++] = u; for(int i = 1; i <= n; i++) { if(map[i][u] == 1) { out[i]--; if(out[i] == 0) que.push(i); } } } if(cnt == n+1) return 1; return 0; } int main() { int test; scanf(%d,&test); while(test--) { scanf(%d %d,&n,&m); memset(out,0,sizeof(out)); memset(map,0,sizeof(map)); int flag = 1; for(int i = 0; i < m; i++) { int a,b; scanf(%d %d,&a,&b); if(!map[a][b]) { map[a][b] = 1; out[a]++; } if(a == b) flag = 0; } if(!flag) { printf(-1 ); continue; } int tmp[210]; int ans = toposort(); if(ans == 0) printf(-1 ); else { for(int i = 1; i <= n; i++) tmp[ topo[i] ] = n+1-i; //编号，tmp[]存的是拓扑排序的逆序. for(int i = 1; i <= n-1; i++) printf(%d ,tmp[i]); //输出编号1~n对应的重量 printf(%d ,tmp[n]); } } return 0; }