本文共 1294 字，大约阅读时间需要 4 分钟。
给n个求再个m个条件，a比b轻，找出n个求每个对应的最小重量，
同时保证1尽量小。2尽量小。。。
拓扑排序，反向建图。
刚开始正向建图没理解。
看题解才懂，题意要求1的重量尽量小，2的重量也尽量小。
所有并不是说当前判定的某几个小。
即不能按编号小的球，重量一定小来求。
所以反向建图，编号大的球重量一定大，这样跑拓扑排序就行了。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 200 + 10;vector G[MAXN];int in[MAXN], res[MAXN];int n, m;void Init(){ for (int i = 1;i <= n;i++) G[i].clear(); memset(in, 0, sizeof(in)); memset(res, 0, sizeof(res));}bool Tupo(){ priority_queue que; for (int i = 1;i <= n;i++) if (in[i] == 0) que.push(i); int pos = n; while (!que.empty()) { int u = que.top(); que.pop(); res[u] = pos--; for (int i = 0;i < G[u].size();i++) { if (--in[G[u][i]] == 0) que.push(G[u][i]); } } if (pos == 0) return true; return false;}int main(){ int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); Init(); int l, r; for (int i = 1;i <= m;i++) { scanf("%d%d", &l, &r); G[r].push_back(l); ++in[l]; } if (Tupo()) { printf("%d", res[1]); for (int i = 2;i <= n;i++) printf(" %d", res[i]); printf("\n"); } else printf("-1\n"); } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10717264.html