hdu--1285 && 4857 --正向 || 逆向拓扑排序 && 优先队列

头太晕了 喝了太多 ..

就想提一点 对于 拓扑排序的这2题 为什么一个是正向 一个是逆向

主要是看题目要求  因为拓扑排序的结果总是有很多种存在的

一般来说 它会让你输出它指定要求的形式的答案

那么 如果是按字典序输出 就是 greater<int> 情况下的优先队列 并且 正向

  如果是尽量使小的数字 靠前输出 而不是追求 字典序 可以考虑 逆向拓扑 逆向输出

但 这些都不是唯一的 一定要分析好题目

曾经 看过一个讲动态规划的word  说拓扑是为DP作准备的 似乎有点道理

这两题 代码 实在太相像了 我都嫌丢人了..........

 1 //正向拓扑排序
 2 #include <iostream>
 3 #include <cstring>
 4 #include <vector>
 5 #include <queue>
 6 using namespace std;
 7
 8 int n;
 9 const int size = 520;
10 vector<int>ve[size];
11 priority_queue<int,vector<int>,greater<int> >q;
12 int in[size];
13 int arr[size];
14
15 void init( )
16 {
17     for( int i = 0 ; i<size; i++ )
18     {
19         in[i] = 0;
20         ve[i].clear();
21     }
22 }
23
24 void topo( )
25 {
26     int cnt = 0 , now , u;
27     for( int i = 1 ; i<=n ; i++ )
28     {
29         if( in[i] == 0 )
30         {
31             q.push(i);
32         }
33     }
34     while( !q.empty() )
35     {
36         now = q.top();
37         q.pop();
38         arr[cnt++] = now;
39         for( int i = 0 ; i<ve[now].size() ; i++ )
40         {
41             u = ve[now][i];
42             in[u] --;
43             if( in[u] == 0 )
44             {
45                 q.push(u);
46             }
47         }
48     }
49     for( int i = 0 ; i<cnt-1 ; i++ )
50     {
51         cout << arr[i] << " ";
52     }
53     cout << arr[cnt-1] << endl;
54 }
55
56 int main()
57 {
58     cin.sync_with_stdio(false);
59     int m , x , y;
60     while( cin >> n >> m )
61     {
62         init();
63         while( m-- )
64         {
65             cin >> x >> y;
66             ve[x].push_back(y);
67             in[y] ++;
68         }
69         topo();
70     }
71     return 0;
72 }

 1 //逆向拓扑排序
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #include <vector>
 6 using namespace std;
 7
 8 int n;
 9 const int size = 30010;
10 int in[size];
11 int arr[size];
12 vector<int>ve[size];
13 priority_queue<int,vector<int>,less<int> >q;
14
15 void init( )
16 {
17     for( int i = 1 ; i<=n ; i++ )
18     {
19         ve[i].clear();
20         in[i] = 0;
21     }
22 }
23
24 void topo( )
25 {
26     int cnt = 0;
27     for( int i = 1 ; i<=n ; i++ )
28     {
29         if( in[i] == 0 )
30         {
31             q.push(i);
32         }
33     }
34     while( !q.empty() )
35     {
36         int now = q.top();
37         q.pop();
38         arr[cnt++] = now;
39         for( int i = 0 ; i<ve[now].size() ; i++ )
40         {
41             int u = ve[now][i];
42             in[u] --;
43             if( in[u] == 0 )
44             {
45                 q.push(u);
46             }
47         }
48     }
49     for( int i = cnt-1 ; i>=1 ; i-- )
50     {
51         cout << arr[i] << " ";
52     }
53     cout << arr[0] << endl;
54 }
55
56 int main()
57 {
58     cin.sync_with_stdio(false);
59     int t , m , x , y;
60     cin >> t;
61     while( t-- )
62     {
63         cin >> n >> m;
64         init( );
65         while( m-- )
66         {
67             cin >> x >> y;
68             in[x] ++;
69             ve[y].push_back(x);
70         }
71         topo();
72     }
73     return 0;
74 }

today:

  一年之前 我喝醉了 你陪我去南湖边吹风

  一年之后 我喝醉了 我陪他们去ktv .....  

hdu--1285 && 4857 --正向 || 逆向拓扑排序 && 优先队列,布布扣,bubuko.com

时间: 08-10

hdu--1285 && 4857 --正向 || 逆向拓扑排序 && 优先队列的相关文章

hdu 4857 逃生 (拓扑排序+优先队列)

逃生 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 688    Accepted Submission(s): 190 Problem Description 糟糕的事情发生啦,现在大家都忙着逃命.但是逃命的通道很窄,大家只能排成一行. 现在有n个人,从1标号到n.同时有一些奇怪的约束条件,每个都形如:a必须在b之前.同时,社会是不平

HDU[1285]确定比赛名次 拓扑排序

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1285 题目大意:某人知道N个队伍M场比赛的胜负结果,要求输出N个队伍的名次(id为第二关键字). 核心思想:转化为图论问题,进行拓扑排序.步骤1.选定入度为0的点 2.删除该点与关联边 3.重复该过程 代码如下: //拓扑排序 (1.选入度为0的点.2.删除该点及关联边 3.重复该过程) #include <iostream> #include <memory.h> using nam

HDU 1285 确定比赛名次(拓扑排序基础)

题目大意: 题目是说,给你一个n个节点的有向无环图,然后,对于这个无环图,我们对他进行拓扑排序,使得拓扑排序中的序列按照字典序的方式输出. 解题思路: 直接套用toposort()模板... 先说说toposort()的含义: 拓扑排序就是说,我们在一完成一项工程的时候,这个工程分为了很多的子工程,我们不可能每次都一下完成很多的工程,我们要按照一定事 务之间的内在联系来完成相应的工程,比如你要完成A工程,那么你必须先完成B工程,所以说B的优先级高于A.那么我们有建图.. 代码: 1 # incl

HDU 1285 确定比赛名次 拓扑排序(邻接矩阵 邻接表

确定比赛名次 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Description 有N个比赛队(1<=N<=500),编号依次为1,2,3,....,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前.现在请你编程序确定排名. Input 输

hdu 4857 逃生 (拓扑排序+保证最小在前面)

逃生 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 74    Accepted Submission(s): 13 Problem Description 糟糕的事情发生啦,现在大家都忙着逃命.但是逃命的通道很窄,大家只能排成一行. 现在有n个人,从1标号到n.同时有一些奇怪的约束条件,每个都形如:a必须在b之前. 同时,社会是不平

HDU 3213 Box Relations(拓扑排序构造)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3231 题意:有n个长方体,四种限制条件.(1)I x y x和y有相交:(2)X/Y/Z  x y x的最大X/Y/Z坐标小于y的最大X/Y/Z.构造出这样的n个长方体. 思路:首先,XYZ三个方向是可以分开考 虑的.那么我们可以一个个分别求解.将每个长方体拆成左上角右下角两个点,我们假设现在考虑X方向,也即是一个长方体对应两个X方向的点,共2*n个点, 边<i,j>表示i小于j,那么首先有边&l

hdu4857 逃生 反拓扑排序+优先队列, 靠前的数字的优先输出.

逃生 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 734    Accepted Submission(s): 199 Problem Description 糟糕的事情发生啦,现在大家都忙着逃命.但是逃命的通道很窄,大家只能排成一行. 现在有n个人,从1标号到n.同时有一些奇怪的约束条件,每个都形如:a必须在b之前. 同时,社会是

HDU 5638 拓扑排序+优先队列

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5638 题意: 给你一个DAG图,删除k条边,使得能个得到字典序尽可能小的拓扑排序 题解: 把拓扑排序的算法稍微改一下,如果某个顶点的入度小于k也把它加到优先队列里面去. k减小后队列里面会有些点不满足<=k,直接踢出来就好了. 代码: #include<iostream> #include<cstring> #include<cstdio> #include<

hdu 5195 DZY Loves Topological Sorting BestCoder Round #35 1002 [ 拓扑排序 + 优先队列 || 线段树 ]

传送门 DZY Loves Topological Sorting Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 221    Accepted Submission(s): 52 Problem Description A topological sort or topological ordering of a directed