两次入坑逆向拓扑序（POJ 3687 Labeling Balls and HDU 4857 逃生）

本文主要是介绍两次入坑逆向拓扑序（POJ 3687 Labeling Balls and HDU 4857 逃生），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一次跳坑

POJ 3687 Labeling Balls

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:

No two balls share the same label.
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

问题概述
有 N 个重量 1~N 不等的球， 将其1~N 编号。题目给出 M 个条件 a,b， 表示 a 号球比 b 号球轻，然后输出小球重量由小到大的编码排序。开始我的理解是这样的(；′⌒`)然后复杂的蹦坑模式就开始了。
1、审题很不认真的一点，输出的不是小球的编号，而是小球的重量，是按照小球从编号 1~N 的顺序输出小球重量。
2、这个题目用入度数组加正向拓扑是通不过的
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…
这个要求是让编号小的尽量排在前面，如果正向拓扑，会存在编号较小的点被更大的点挡住的问题；所以通过逆向拓扑加上优先队列大顶堆维护的方法，每次都选出来编号较大的点，编号小的点自然就在后面啦，再按照要求选择顺序输出结果。

测试数据：
方法选择：测试数据（5 4 1 4 4 2 2 3 3 5） 正向拓扑：1->4->2，5->3->2可得结果 1 4 5 3 2，显然这是不对的，因为1 4 与 5 3 之间没有相互约束，按照编号小应在前的原则，5 3 应位于 4 之前。则答案为最后逆向拓扑序的结果 1 5 3 4 2；
获得最终结果：测试数据（5 4 1 4 4 2 5 3 3 2） 逆向拓扑序后得 out[]={ 2(i=0) 4(i=1) 3(i=2) 5(i=3) 1(i=4) } （按照重量由大到小），所以编号为2的小球是重量最大的小球，重量即为 (m-i)，即为 realout[2]；同理便可得到最终的数组 realout[]。

代码实现

#include <iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
vector<int>a[206];
int in[206];            //入度数组
int m,n,countt;
int out[206];              //逆向拓扑序的结果（按照重量由大到小）
int realout[206];        //小球按照编号 1~N 分别对应的重量
int toposort()
{countt=0;priority_queue<int>qu;for(int i=1; i<=m; i++)if(!in[i])qu.push(i);while(!qu.empty()){int temp=qu.top();qu.pop();out[countt++]=temp;for(int i=0; i<a[temp].size(); i++){int z=a[temp][i];if(--in[z]==0)qu.push(z);}}if(countt>=m) return true;elsereturn false;
}
int main()
{int T,x,y;scanf("%d",&T);while(T--){scanf("%d %d",&m,&n);for(int i=0; i<=m; i++)a[i].clear();memset(in,0,sizeof(in));for(int i=0; i<n; i++){scanf("%d %d",&x,&y);a[y].push_back(x);in[x]++;}if(!toposort())printf("-1\n");else{for(int i=0; i<m; i++)realout[out[i]]=m-i;       //获取重量for(int i=1; i<m; i++)printf("%d ",realout[i]);printf("%d\n",realout[m]);}}return 0;
}

第二次跳坑

HDU 4857 逃生

Problem Description
糟糕的事情发生啦，现在大家都忙着逃命。但是逃命的通道很窄，大家只能排成一行。

现在有n个人，从1标号到n。同时有一些奇怪的约束条件，每个都形如：a必须在b之前。
同时，社会是不平等的，这些人有的穷有的富。1号最富，2号第二富，以此类推。有钱人就贿赂负责人，所以他们有一些好处。

负责人现在可以安排大家排队的顺序，由于收了好处，所以他要让1号尽量靠前，如果此时还有多种情况，就再让2号尽量靠前，如果还有多种情况，就让3号尽量靠前，以此类推。

那么你就要安排大家的顺序。我们保证一定有解。

Input
第一行一个整数T(1 <= T <= 5),表示测试数据的个数。
然后对于每个测试数据，第一行有两个整数n(1 <= n <= 30000)和m(1 <= m <= 100000)，分别表示人数和约束的个数。

然后m行，每行两个整数a和b，表示有一个约束a号必须在b号之前。a和b必然不同。

Output
对每个测试数据，输出一行排队的顺序，用空格隔开。

Sample Input
1
5 10
3 5
1 4
2 5
1 2
3 4
1 4
2 3
1 5
3 5
1 2

Sample Output
1 2 3 4 5

问题概述
和上一个题目相似，再次跳坑的感觉很不好啊，开始怀疑自己的理解能力了(；′⌒`)正向拓扑提交了好多次，爬起来！依旧是编号小的尽量往前放，逆向拓扑排序，倒序输出！

代码实现

#include <iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 30006
vector<int>a[maxn];
int in[maxn],m,n,countt;
int out[maxn],realout[maxn];
int toposort()
{countt=0;priority_queue<int>qu;for(int i=1; i<=m; i++)if(!in[i])qu.push(i);while(!qu.empty()){int temp=qu.top();qu.pop();out[countt++]=temp;for(int i=0; i<a[temp].size(); i++){int z=a[temp][i];if(--in[z]==0)qu.push(z);}}
}
int main()
{int T,x,y;scanf("%d",&T);while(T--){scanf("%d %d",&m,&n);for(int i=0; i<=m; i++)a[i].clear();memset(in,0,sizeof(in));for(int i=0; i<n; i++){scanf("%d %d",&x,&y);a[y].push_back(x);in[x]++;}toposort();for(int i=m-1;i>0;i--)printf("%d ",out[i]);printf("%d\n",out[0]);}return 0;
}

这篇关于两次入坑逆向拓扑序（POJ 3687 Labeling Balls and HDU 4857 逃生）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---