首页 > 代码库 > [ACM] POJ 3687 Labeling Balls (拓扑排序,逆向建边)

[ACM] POJ 3687 Labeling Balls (拓扑排序,逆向建边)

Labeling Balls
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10161 Accepted: 2810

Description

Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 toN 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 withb".

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 nextM line each contain two integers a and b indicating the ball labeled witha must be lighter than the one labeled with b. (1 ≤ a, bN) 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 labelN. 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

Source

POJ Founder Monthly Contest – 2008.08.31, windy7926778


解题思路:

每做一道题都可以学到新的思路。

由编号1—N的N个小球,重量也为1—N(容易混淆),给出一些限制条件,a  b,代表着编号为a的小球比编号为b的小球的重量小,根据限制条件,给小球分配重量,最后输出的是编号1—N的小球的重量。如果有多种方法,那么编号小的小球重量尽量小。

拓扑排序有多种写法,可以用栈,可以用队列,也可以用循环,不同的情况下用不同的方法。如本题就可以用循环,外层循环也代表着需要分配的重量。


这个题不能用正向建边,拓扑排序。。没想到这一点。。因为要求编号小的小球重量尽量小,在正向拓扑排序有多种方法的时候,不能保证这一点。做法为逆向建边,每次找入度为0的编号,重量从大到小进行赋值。最后还要提一点,大数据还得用scanf,时间差距太大了。。

下面两篇博文的解释我觉得不错:

http://www.cnblogs.com/rainydays/archive/2011/07/20/2112047.html

分析:拓扑排序,注意根据题的要求,要先保证1号球最轻,如果我们由轻的向重的连边,然后我们依次有小到大每次把重量分给一个入度为0的点,那么在拓扑时我们面对多个入度为0的点,我们不知道该把最轻的分给谁才能以最快的速度找到1号(使1号入度为0),并把当前最轻的分给1号。所以我们要由重的向轻的连边,然后从大到小每次把一个重量分给一个入度为0的点。这样我们就不用急于探求最小号。我们只需要一直给最大号附最大值,尽量不给小号赋值,这样自然而然就会把轻的重量留给小号。(转)

http://blog.163.com/xiaohuang_17/blog/static/5458538620099874334826/(转载)

PKU 3687 在基本的拓扑排序的基础上又增加了一个要求:编号最小的节点要尽量排在前面;在满足上一个条件的基础上,编号第二小的节点要尽量排在前面;在满足前两个条件的基础上,编号第三小的节点要尽量排在前面……依此类推。(注意,这和字典序是两回事,不可以混淆。)

    如图 1 所示,满足要求的拓扑序应该是:6 4 1 3 9 2 5 7 8 0。



图 1 一个拓扑排序的例子


    一般来说,在一个有向无环图中,用 BFS 进行拓扑排序是比较常见的做法,如算法 1 所示。但是它不一定能得到本题要求的拓扑序。

1. 把所有入度为 0 的节点放进队列 Q
2. WHILE: Q 不是空队列
3.     从 Q 中取出队列首元素 a,把 a 添加到答案的尾部。
4.     FOR:所有从 a 出发的边 a → b
5.         把 b 的入度减 1。如果 b 的入度变为 0,则把 b 放进队列 Q。


算法 1 用 BFS 进行拓扑排序


    为了解决本问题,下面让我来探究一下拓扑序的一些性质。以图 1 为例,节点 0 毫无疑问排在最后。除了节点 0 以外,有三条互相平行的路径:6 → 4 → 1、 3 → 9 → 2 和 5 → 7 → 8。一条路径上的各个节点的先后关系都是不能改变的,比如路径 6 → 4 → 1 上的三个节点在拓扑序中,一定是 6 在最前,1在最后。但是,互相平行的各条路径,在总的拓扑序中任意交错都是合法的。比如,以下都是图 1 的合法拓扑序:

    6 4 1 3 9 2 5 7 8 0、 3 6 9 4 5 1 7 8 2 0、 5 6 4 7 3 8 1 9 2 0、 3 5 6 4 1 7 9 2 8 0、 6 5 7 8 4 3 9 21 0。

    怎么才能找出题目要求的拓扑序呢?在这里,我想用字典序最先的拓扑序来引出这个算法。算法 2 可以求出字典序最先的拓扑序。

1. 把所有入度为 0 的节点放进优先队列 PQ
2. WHILE: PQ 不是空队列
3.     从 PQ 中取出编号最小的元素 a,把 a 添加到答案的尾部。
4.     FOR:所有从 a 出发的边 a → b
5.         把 b 的入度减 1。如果 b 的入度变为 0,则把 b 放进优先队列 PQ。


算法 2 求出字典序最先的拓扑序


    可见,算法 2 和算法 1 基本一样,只是把队列改成了优先队列。用它求出的图 1 的字典序最先的拓扑序为:3 5 6 4 1 7 8 9 2 0。但是这显然不是本题要求的答案,因为节点 1 的位置还不够靠前。

    算法 2 可以算是一个贪心算法,每一步都找编号最小的节点。但是对于图 1 中的三条路径,头的编号比较小的,不一定要先出队列。正确的步骤应该如下:

  1. 节点 0 的位置是铁定在最后的,不用考虑。只考虑剩下的三条路径。
  2. 先找编号最小的,节点 1。把它和它所在的路径中位于它前面的节点全部拿出来。目前的答案是 64 1,这样, 节点 1 就尽量靠前了。
  3. 再找剩下的节点中编号最小的,节点 2。把它和它所在的路径中位于它前面的节点全部拿出来。目前的答案是 6 4 1 3 9 2 ,这样,节点 2 就尽量靠前了。
  4. 只剩下一条路径了,只能依次把其中的节点拿出来。最后答案就是 6 4 1 3 9 2 5 7 8 0。

    显然,算法 2 的贪心策略对于这个问题是不可行的。不能着眼于每条路径的头,而是要找编号最小的节点在哪条路径上,优先把这条路径拿出来。但问题在于,在 BFS 的过程中,我们只能看到每条路径的头,看不到后面的节点,这该怎么办呢?

    让我们换个角度想一想,节点 3 和 6,应该是 6 先出队列,因为节点 1 在 6 的后面。这和节点 3 和 6 的编号大小没有任何关系。但是,再看另外两条路径的尾部,节点 2 和 8,可以肯定地说,2 一定先出队列,因为它们后面都没有别的节点了,这个时候完全以这两个节点本身的编号大小决定顺序。归纳起来就是说,对于若干条平行的路径,小的头部不一定排在前面,但是大的尾部一定排在后面。于是,就有了算法 3

1. 把所有出度为 0 的节点放进优先队列 PQ
2. WHILE: PQ 不是空队列
3.     从 PQ 中取出编号最大的元素 a,把 a 添加到答案的头部。
4.     FOR:所有指向 a 的边 b → a
5.        把 b 的出度减 1。如果 b 的出度变为 0,则把 b 放进优先队列 PQ。   


算法 3 求出本题目要求的拓扑序

代码:
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int maxn=210;
int graph[maxn][maxn];
int indegree[maxn];
int output[maxn];
int n,m;
bool ok;//判断是否可以。

void topo()
{
    for(int i=n;i>=1;i--)
    {
        int MinNum=-1;
        for(int j=n;j>=1;j--)//找入度为0的编号,这里是编号最大的入度为0的点,和用优先队列效果是一样的。
            if(!indegree[j])
        {
            MinNum=j;
            indegree[j]--;//别忘了这一句
            break;
        }
        if(MinNum==-1)//找不到入度为0的点,说明有环 
        {
            ok=0;
            return ;
        }
        
        output[MinNum]=i;//重量i分给编号为MinNum的球
        
        for(int j=1;j<=n;j++)
            if(graph[MinNum][j])
            indegree[j]--;//与编号为0的点相连的点入度--
    }
}

int main()
{
    int t;cin>>t;
    int a,b;
    while(t--)
    {
        memset(indegree,0,sizeof(indegree));
        memset(graph,0,sizeof(graph));
        ok=1;
        scanf("%d%d",&n,&m);
        if(ok==0)
            continue;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            if(graph[a][b])//有逆向边
            {
                ok=0;
                continue;
            }

            if(!graph[b][a])//逆向建边
            {
                graph[b][a]=1;
                indegree[a]++;
            }
        }
        topo();
        if(ok)
        {
            for(int i=1;i<n;i++)
                printf("%d ",output[i]);
            printf("%d\n",output[n]);
        }
        else
            printf("-1\n");
    }
    return 0;
}