首页 > 代码库 > HDU 4857 逃生 (反向拓扑排序 & 容器实现)

HDU 4857 逃生 (反向拓扑排序 & 容器实现)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4857

逃生

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4505    Accepted Submission(s): 1282

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
 
题意:n个结点,m个拓扑关系(a,b)表示a必须排在b前面,在满足m个拓扑关系关系的前提下使得小的结点尽可能的排在前面。
也就是说我们现在要从1号结点开始考虑,如果要排1号结点,根据拓扑关系,首先必须排哪些结点,如果排好了1号结点,则继续考虑2号结点 ,3号结点。。 
我们先看两个例子: 
存在拓扑关系: 
5 -> 3 -> 1 
6 -> 4 -> 2 
直接拓扑排序的结果是 5 3 1 6 4 2,结果是正确的(1号尽可能的在前面了) ,看起来好像直接拓扑排序就可以了,
但是为什么提交后却wa了呢,别急,我们再看一个例子: 
6 -> 3 -> 1 
5 -> 4 -> 2 
直接拓扑排序的结果是:5 4 2 6 3 1 ,结果是错误的,因为我们可以把1号安排到更前面的位置 即:6 3 1 5 4 2(正确答案)。 
看到这里应该就知道为什么直接拓扑排序不行了吧,我们分析一下为什么会出现这样的状况,对于多条弧或者边,
我们是先删除弧尾结点比较小的结点即(5号结点比6号结点小,先删除以该点为尾的弧),而这也正是问题所在,
我们希望的是优先删除弧头比较小的弧的(1号结点比2号结点小,因优先删除以1号为头的弧)。 
好了,问题找到了,现在我们在来想如何解决问题,我们可以尝试一下逆向思维,即我们先考虑哪些点应该靠后释放,
这样的话我们就可以把拓扑关系反过来(即弧头和弧尾调换),然后做拓扑排序,
然后我们可以根据原来的弧头(现在变成弧尾)的大小来释放结点,由于现在的问题变成哪些最后释放,
那么就应该优先考虑弧尾(原来的弧头)比较大的,可以通过优先队列来解决。
 
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 using namespace std;
 8 #define maxx 30010
 9 vector <int > vec[maxx];
10 priority_queue <int > q;  //优先队列
11 int num[maxx],in[maxx];
12 int main ()
13 {
14     int t,u,v,m,n,i,j;
15     scanf("%d",&t);
16     while (t --)
17     {
18         scanf("%d%d",&n,&m);
19         for (i = 1; i <= n; i ++)  //清空容器内的数据
20             vec[i].clear();
21         memset(in,0,sizeof(in));   //入度初始化为0
22 
23         for (i = 0; i < m; i ++)
24         {
25             scanf("%d%d",&u,&v);
26             in[u] ++;
27             vec[v].push_back(u);
28         }
29         for (i = 1; i <= n; i ++)   //将入度为0的点加入优先队列
30             if (in[i]==0) q.push(i);
31 
32         j = 0;
33         while(!q.empty())
34         {
35             int k = q.top();
36             q.pop();
37             num[j ++] = k;
38             int len = vec[k].size();
39             for (i = 0; i < len; i ++)  // 删除与度数为0的节点相关联的边
40             {
41                 int l = vec[k][i];
42                 in[l] --;
43                 if (in[l]==0)
44                     q.push(l);
45             }
46         }
47         for (i = j-1; i >= 0; i --)
48         {
49             if (i==0)
50                 printf("%d",num[i]);
51             else
52                 printf("%d ",num[i]);
53         }
54         printf("\n");
55     }
56     return 0;
57 }

 

HDU 4857 逃生 (反向拓扑排序 & 容器实现)