首页 > 代码库 > hdu 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之前。
同时，社会是不平等的，这些人有的穷有的富。1号最富，2号第二富，以此类推。有钱人就贿赂负责人，所以他们有一些好处。
负责人现在可以安排大家排队的顺序，由于收了好处，所以他要让1号尽量靠前，如果此时还有多种情况，就再让2号尽量靠前，如果还有多种情况，就让3号尽量靠前，以此类推。
那么你就要安排大家的顺序。我们保证一定有解。
现在有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必然不同。
然后对于每个测试数据，第一行有两个整数n(1 <= n <= 30000)和m(1 <= m <= 100000)，分别表示人数和约束的个数。
然后m行，每行两个整数a和b，表示有一个约束a号必须在b号之前。a和b必然不同。
Output
对每个测试数据，输出一行排队的顺序，用空格隔开。
Sample Input
15 103 51 42 51 23 41 42 31 53 51 2
Sample Output
1 2 3 4 5
Author
CLJ
题目意思不用多说吧，陈立杰出的题，果然很不错，当天比赛BC过了的只有9个人。觉得是一道非常不错的拓扑排序题吧。
解题思路：因为既要满足一定的约束顺序，又要满足一定的优先顺序。反向建图，先把度为0且下标值大的输出到一个排序数组当中，然后再反向输出这个数组。
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <queue>#define MAXN 30005using namespace std;struct ArcNode{ int to; struct ArcNode * next;};struct Node{ int x; friend bool operator < (Node a, Node b) { return b.x > a.x; }};struct ArcNode * List[MAXN];int Indegree[MAXN], Top[MAXN];void Topological(int n){ struct ArcNode * temp; struct Node node; priority_queue <Node> Q; for(int i = 1; i<=n; i++) //将度为0的节点压入优先队列中 { if(0 == Indegree[i]) { node.x = i; Q.push(node); } } for(int i = 1; i<=n; i++) { node = Q.top(); Q.pop(); Top[i] = node.x; //按优先值大小输出 temp = List[node.x]; while(NULL != temp) { int k = temp->to; if(--Indegree[k] == 0) { node.x = k; Q.push(node); } temp = temp->next; } }}int main(){ int n, m, u, v, T; struct ArcNode * temp; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); memset(List, 0, sizeof(List)); memset(Indegree, 0, sizeof(Indegree)); memset(Top, 0, sizeof(Top)); while(m--) { scanf("%d%d", &u, &v); Indegree[u]++; //反向建图 temp = (struct ArcNode *)malloc(sizeof(struct ArcNode)); temp->to = u; temp->next = NULL; if(List[v] == NULL) List[v] = temp; else { temp->next = List[v]; List[v] = temp; } } Topological(n); for(int i = n; i>1; i--) printf("%d ", Top[i]); printf("%d\n", Top[1]); } return 0;}
hdu 4857 逃生 （拓扑排序+优先队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。