POJ 3687 Labeling Balls

题意：

有n个小球，权重分别为1~n。现在要为这些小球贴上1~n的标签，规则是标签1所对应的小球的权重应尽量小，其次是标签2...接下来会有m个要求，就是标签a所贴小球的权重必须小于标签b所贴小球的权重。

思路：

拓扑排序。

首先我考虑的是正向的拓扑排序，建好图后每次选择度数为0的最小的顶点，为它贴上当前权重最小的小球。但是这样做有缺陷，举个例子来说：

5 3
1 4
4 2
3 5
正确答案应该是输出1 3 4 2 5，但是如果按照我的做法去做的话，输出的是1 4 2 3 5。因为2在4后面，先处理了3，这样导致了标签2所贴球的权重较大，最优的是先处理4，这样2就能有较小值。
于是考虑用反向拓扑来做，每次将小的那端的度数+1，每次选择度数为0的最大的顶点，为它贴上当前权重最大的小球。这样就保证了大标签贴在了权重大的球上。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 200 + 5;
 8 
 9 int n, m;
10 int g[maxn][maxn];
11 int indegree[maxn];
12 int ans[maxn];
13 
14 int tuopu()
15 {
16     int cnt = n;
17     for (int i = 1; i <= n; i++)
18     {
19         int num = 0, loc;
20         for (int j = 1; j <=n;j++)
21         {
22             if (indegree[j] == 0)
23             {
24                 num++;
25                 loc = j;
26             }
27         }
28         if (num == 0)     return -1;
29         ans[loc] = cnt--;
30         indegree[loc] = -1;
31         for (int j = 1; j <= n;j++)
32         if (g[loc][j])   indegree[j]--;
33     }
34     return 1;
35 }
36 
37 int main()
38 {
39     //freopen("D:\txt.txt", "r", stdin);
40     int T;
41     int x, y;
42     scanf("%d", &T);
43     while (T--)
44     {
45         memset(g, 0, sizeof(g));
46         memset(indegree, 0, sizeof(indegree));
47         memset(ans, 0, sizeof(ans));
48         bool flag = true;
49         scanf("%d%d", &n, &m);
50         while (m--)
51         {
52             scanf("%d%d", &x, &y);
53             if (x == y)  flag = false;
54             //反向拓扑
55             if (!g[y][x])     //这里需要注意一下重边的问题
56             {
57                 g[y][x] = 1;
58                 indegree[x]++;
59             }
60         }
61         if (flag)
62         {
63             int p = tuopu();
64             if (p == -1)     printf("-1
");
65             else
66             {
67                 for (int i = 1; i < n; i++)
68                     cout << ans[i] << " ";
69                 cout << ans[n] << endl;
70             }
71         }
72         else printf("-1
");
73     }
74     return 0;
75 }