POJ 3687 -- Labeling Balls(Topological Sort)

POJ 3687 -- Labeling Balls(Topological Sort)

Description

Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:

1. No two balls share the same label.
2. The labeling satisfies several constrains like "The ball labeled with a is lighter than the one labeled with b".

Can you help windy to find a solution?

Input

The first line of input is the number of test case. The first line of each test case contains two integers, N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ 40,000). The next M line each contain two integers a and b indicating the ball labeled with a must be lighter than the one labeled with b. (1 ≤ a, b ≤ N) There is a blank line before each test case.

Output

For each test case output on a single line the balls' weights from label 1 to label N. If several solutions exist, 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... If no solution exists, output -1 instead.

Sample Input

5

4 0

4 1
1 1

4 2
1 2
2 1

4 1
2 1

4 1
3 2

Sample Output

1 2 3 4
-1
-1
2 1 3 4
1 3 2 4

http://www.2cto.com/kf/201403/288775.html
题意：有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并且数最小的不对的。因为即使该点最小，它后面连着的点未必是最小的。


1. 相互之间有一定的约束关系，会联系到拓扑排序，如果利用拓扑排序去解决本题还需要一定的贪心思想;
2. 因为要保证标号小的球靠前的优先级越高，所以对于正向图拓扑排序，无法满足，比如：<1, 4> <4, 2> <3, 5>
3. 对于反向拓扑排序，用同样的方法只需要保证标号大的球尽量靠后就行了.

把所有出度为 0 的节点放进优先队列 PQ

2. WHILE： PQ 不是空队列

3.     从 PQ 中取出编号最大的元素a，把a添加到答案的头部。

4.     FOR：所有指向 a 的边 b → a

5.        把 b 的出度减 1。如果 b 的出度变为 0，则把 b 放进优先队列 PQ。

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;

}

http://blog.sina.com.cn/s/blog_6c7729450100qxbw.html

解法：建立反向图，即所有边取反向，然后拓扑排序，当有多个入度为0的点时总是先选择label大的点。然后将序列反转。注意此时得到的序列并不是本题的答案，本题答案要求是输出每个点是第几次被选出的。但为了方便叙述，下面将算法得到的最后序列称为答案。

下面用反证法给出本解法的证明：
假设解法得到的答案为F1 F2 F3......Fn，设最优解为R1 R2 R3......Rn。显然最优解为满足原图拓扑序且（把每个值看作字母后）以Rn为下标，n为值的序列字典序最小的解。

设k<=N且Fk!=Rk且任意k<p<=N，Rp==Fp。则必有Fk>Rk，设t<k且Rt==Fk，则序列Rt,Rt+1......Rk 等价于Fk,Rt+1......Rk，记为序列1，显然Fk不是序列1的最小值，因为至少存在一个Rk<Fk。则取t<q<=k，Rq是序列1的最小值，变序列1为Rt+1,Rt+2...Rq,Fk,Rq+1...Rk，记为序列2，显然序列2是合法的，且序列2比序列1更优。因此给定最优解不是最优解，得到矛盾。因此解法得到的答案是最优解。

http://www.verydemo.com/demo_c92_i288942.html

当前入度为 0 的点大于一个时，我们先取数字较大的点（队列内递增）。取出的点按的权值从 N-1递减。

关键：

建边方法，（重） -> （轻）

先确定重量大的点！

1. const int maxn = 220;  
2. struct Edge{  
3.     int v, next;  
4. }edge[maxn*maxn];  
5. int tot, head[maxn];  
6. int n, r, cnt[maxn], in[maxn];  
7. struct P{  
8.     int id, w;  
9. }node[maxn];  
10. void init()  
11. {  
12.     tot = 0;  
13.     memset(head, -1, sizeof(head));  
14.     memset(cnt, 0, sizeof(cnt));  
15.     memset(in, 0, sizeof(in));  
16. }  
17. void add_edge( int u, int v )  
18. {  
19.     edge[tot].v = v;  
20.     edge[tot].next = head[u];  
21.     head[u] = tot++;  
22. }  
23. int queue[maxn], front, rear;  
24. bool cmp2( int a, int b ){ return a > b; }  
25. bool topusort()  
26. {  
27.     int i, u, v, N = n;  
28.     front = rear = 0;  
29.     for(i = 1; i <= n; i++)if(!in[i])  
30.         queue[rear++] = i;  
31.     while( front != rear )  
32.     {  
33.         sort( queue+front, queue+rear, cmp2 );  
34.         u = queue[front++];  
35.         node[front-1].id = u;  
36.         node[front-1].w = N--;  
37.         for(i = head[u]; i != -1; i = edge[i].next)  
38.         {  
39.             v = edge[i].v;  
40.             in[v]--;  
41.             if(!in[v])  
42.                 queue[rear++] = v;  
43.         }  
44.     }  
45.     if(rear == n)return true;  
46.     return false;  
47. }  
48. bool cmp1( P a, P b )  
49. {  
50.     return a.id < b.id;  
51. }  
52. int main()  
53. {  
54.     int i, u, v, T;  
55.     scanf( "%d", &T );  
56.     while( T-- )  
57.     {  
58.         scanf( "%d%d", &n, &r );  
59.         init();  
60.         while( r-- )  
61.         {  
62.             scanf( "%d%d", &u, &v );  
63.             add_edge( v, u );  
64.             in[u]++;  
65.         }  
66.   
67.         if(topusort())  
68.         {  
69.             sort( node, node+n, cmp1 );  
70.             for(i = 0; i < n; i++)  
71.             {  
72.                 if(i == 0)printf( "%d", node[i].w );  
73.                 else printf( " %d", node[i].w );  
74.             }puts("");  
75.         }  
76.         else  
77.             puts("-1");  
78.     }  
79.     return 0;  
80. }

Read full article from 3687 -- Labeling Balls