| 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 to N in such a way that:
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
Source
每做一道题都可以学到新的思路。
由编号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。
一般来说，在一个有向无环图中，用 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 为例，节点 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 和算法
1 基本一样，只是把队列改成了优先队列。用它求出的图 1 的字典序最先的拓扑序为：3 5 6 4 1 7 8 9 2 0。但是这显然不是本题要求的答案，因为节点
1 的位置还不够靠前。
算法 2 可以算是一个贪心算法，每一步都找编号最小的节点。但是对于图
1 中的三条路径，头的编号比较小的，不一定要先出队列。正确的步骤应该如下：
显然，算法 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。 |
#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;
}
[ACM] POJ 3687 Labeling Balls (拓扑排序，逆向建边）,布布扣,bubuko.com
[ACM] POJ 3687 Labeling Balls (拓扑排序，逆向建边）
原文：http://blog.csdn.net/sr_19930829/article/details/37903771