题意:有N个人,M个优先级a,b表示a优先于b。而且每一个人有个编号的优先级。输出顺序。
思路来自:与PKU3687一样
在主要的拓扑排序的基础上又添加了一个要求:编号最小的节点要尽量排在前面;在满足上一个条件的基础上,编号第二小的节点要尽量排在前面;在满足前两个条件的基础上,编号第三小的节点要尽量排在前面……依此类推。(注意,这和字典序是两回事,不能够混淆。
)
如图 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 2 1 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 中的三条路径,头的编号比較小的。不一定要先出队列。正确的步骤应该例如以下:
- 节点 0 的位置是铁定在最后的,不用考虑。仅仅考虑剩下的三条路径。
- 先找编号最小的。节点 1。把它和它所在的路径中位于它前面的节点所有拿出来。眼下的答案是 6 4 1,这样。 节点 1 就尽量靠前了。
- 再找剩下的节点中编号最小的,节点 2。把它和它所在的路径中位于它前面的节点所有拿出来。眼下的答案是 6 4 1 3 9 2 ,这样,节点 2 就尽量靠前了。
- 仅仅剩下一条路径了,仅仅能依次把当中的节点拿出来。最后答案就是 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<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<map> #include<cmath> #include<iostream> #include <queue> #include <stack> #include<algorithm> #include<set> using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define maxn 505 #define mod 1000000007 vector<int>G[30003]; int out[30003]; int n,m,a[30003]; void toposort() { priority_queue<int>q; int len=n; for(int i=1;i<=n;i++) if(out[i]==0) q.push(i); while(!q.empty()) { int tmp=q.top(); a[len--]=tmp; q.pop(); for(int i=0;i<G[tmp].size();i++) { out[G[tmp][i]]--; if(out[G[tmp][i]]==0) q.push(G[tmp][i]); } } for(int i=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int a,b; for(int i=1;i<=n;i++) out[i]=0,G[i].clear(); while(m--) { scanf("%d%d",&a,&b); G[b].push_back(a); out[a]++; } toposort(); } return 0; } /* 1 5 10 3 5 1 4 2 5 1 2 3 4 1 4 2 3 1 5 3 5 1 2 */
本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5135447.html,如需转载请自行联系原作者