Coder Space

PKU 3687 Labeling Balls--- 反向拓扑排序+优先队列

 

 

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

如图 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 以外,有三条互相平行的路径:641 392 578。一条路径上的各个节点的先后关系都是不能改变的,比如路径 641 上的三个节点在拓扑序中,一定是 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 中的三条路径,头的编号比较小的,不一定要先出队列。正确的步骤应该如下:

  1. 节点 0 的位置是铁定在最后的,不用考虑。只考虑剩下的三条路径。
  2. 先找编号最小的,节点 1。把它和它所在的路径中位于它前面的节点全部拿出来。目前的答案是 6 4 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 求出本题目要求的拓扑序

  1 /*
  2  * 3687.cc
  3  *
  4  *  Created on: May 17, 2010
  5  *      Author: LR-Zhi
  6  */
  7 /*
  8  * 题意:对标记1-N的球,赋重,使其满足一定的重量大小要求。实质是根据给出的关系建图,拓扑排序,排序中标号排在的位置,即为其应赋的重量。
  9  *      本题在基本的拓扑排序前提下多加一个条件,编号小的点尽量排在前面。
 10  *
 11  * 易知,典型的拓扑排序满足不了题目小号排前的要求,可以采用反向拓扑排序,加优先队列完成。
 12  */
 13 
 14 #include<iostream>
 15 #include<queue>
 16 
 17 using namespace std;
 18 
 19 const int MAXN = 201;
 20 
 21 bool G[MAXN][MAXN];
 22 int degree[MAXN];
 23 int sorted[MAXN];
 24 
 25 bool TopSort(int n)
 26 {
 27     priority_queue<int> q;
 28     int cur;
 29     int nElem = n;
 30 
 31     for(int i = 1; i <= n; i++)
 32     {
 33         if(degree[i] == 0)
 34         {
 35             q.push(i);
 36         }
 37     }
 38     while(!q.empty())
 39     {
 40         cur = q.top();
 41         sorted[nElem--= cur;
 42         q.pop();
 43 
 44         for(int j = 1; j <= n; j++)
 45         {
 46             if(G[j][cur])
 47             {
 48                 degree[j]--;
 49                 if(degree[j] == 0)
 50                 {
 51                     q.push(j);
 52                 }
 53             }
 54         }
 55     }
 56     if(nElem != 0)        //存在环
 57     {
 58         return false;
 59     }
 60     return true;
 61 }
 62 
 63 int main()
 64 {
 65     int T,N,M;
 66     int a,b;
 67 
 68     int i,j;
 69 
 70     cin>>T;
 71     while(T--)
 72     {
 73         cin>>N>>M;
 74         for(i = 1; i <= N; i++)
 75         {
 76             for(j = 1; j <= N; j++)
 77             {
 78                 G[i][j] = false;
 79             }
 80             degree[i] = 0;
 81         }
 82         for(i = 0; i < M; i++)
 83         {
 84             cin>>a>>b;
 85             if(!G[a][b])        //注意,有重边,计degree时不能多计
 86             {
 87                 G[a][b] = true;
 88                 degree[a]++;
 89             }
 90         }
 91 
 92         if(!TopSort(N))
 93         {
 94             cout<<"-1"<<endl;
 95         }
 96         else
 97         {
 98             int weigh[MAXN];
 99             for(i = 1; i <= N; i++)
100             {
101                 weigh[sorted[i]] = i;
102             }
103             for(i = 1; i <= N; i++)
104             {
105                 cout<<weigh[i]<<" ";
106             }
107             cout<<endl;
108         }
109     }
110 }
111 
112 

posted on 2010-05-17 18:35 David Liu 阅读(1273) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论