pku 3687 Labeling Balls 逆序拓扑排序

﹏ヽ暗。殇╰゛Y 2022-08-09 13:59 4阅读 0赞

这题的题意确实有点难懂.

For each test case output on a single line the balls' weights from label 1 to label *N*. If several solutions exist:

要注意要求输出的是球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:

而且要求当有多解时,球1的质量最轻,then球2的质量最轻,...

也即是说,球号较小的球质量应取到最小.

读懂题意,再用逆序的拓扑排序,问题就不难了.

\#include <iostream> \#include <algorithm> \#include <vector> using namespace std; int edge\[201\]\[201\]; int inDegree\[201\]; int N, M; vector<int> v; vector<int> save; //拓扑排序 bool TopoOrder() \{ v.clear(); save.clear(); memset(inDegree, 0, sizeof(inDegree)); int i, j; for(i = 1; i <= N; ++i) for (j = 1; j <= N; ++j) \{ if(edge\[i\]\[j\]) inDegree\[j\]++; \} for (i = 1; i <= N; ++i) if(inDegree\[i\] == 0) v.push\_back(i); int cnt = 0; while (!v.empty()) \{ int max = -1; int index = 0; for(i = 0; i < v.size(); ++i) if(v\[i\] > max) \{ max = v\[i\]; index = i; \} save.push\_back(max); v.erase(v.begin()+index); cnt++; for (i = 1; i <= N; ++i) \{ if(edge\[max\]\[i\] && (--inDegree\[i\]) == 0) v.push\_back(i); \} \} if(cnt < N) return false; return true; \} int main() \{ int cases; int v1, v2; scanf("%d", &cases); while(cases--) \{ memset(edge, 0, sizeof(edge)); scanf("%d%d", &N, &M); for (int i = 1; i <= M; ++i) \{ scanf("%d%d", &v1, &v2); edge\[v2\]\[v1\] = 1; \} if(M == 0) \{ for (int i = 1; i <= N; ++i) \{ printf("%d ", i); \} printf("/n"); continue; \} if(!TopoOrder()) printf("-1/n"); else \{ for (int i = 0; i < save.size(); ++i) printf("%d ", save.size()-(find(save.begin(), save.end(), i+1)-save.begin())); printf("/n"); \} \} return 0; \}