HDU 4857 逃生(拓扑排序,优先队列,容器)

2023-12-13 20:08

本文主要是介绍HDU 4857 逃生(拓扑排序,优先队列,容器),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

逃生

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


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

Author
CLJ

Source
BestCoder Round #1

Recommend
We have carefully selected several similar problems for you:   5803  5802  5801  5800  5799 


思路:

跟着学姐的思路用的是邻接表,建立反向拓扑:

因为:输入3 1 应该是3 1  2,如果是按普通的正向拓扑排序做的就是2 在最前面 即 2  3  1(不正确)。


之前参考的是容器的思想:

第一次使用 vector 容器,之前宇神讲过一次(.......),看了会题解,敲了两个小时。

容器要看,优先队列还要去复习下微笑


代码:邻接表+优先队列

#include<stdio.h>
#include<string.h>
#include<queue>
const int MYDD=1103+1e5;
using namespace std;int head[MYDD];
int indegree[MYDD];
int numedge;//边数
struct EDGE {int v,next;
} edge[MYDD*2];void init() {//邻接表的初始化memset(head,-1,sizeof(head));memset(indegree,0,sizeof(indegree));numedge=0;
}void addedge(int a,int b) {EDGE T= {a,head[b]};edge[numedge]=T;head[b]=numedge++;
}int ans[MYDD];//记录排序顺序
void TopoSort(int x) {priority_queue<int> Q;//构造优先队列int now,dd=0;//当前节点,ans[]数组下标for(int j=1; j<=x; j++)if(!indegree[j])        Q.push(j);while(!Q.empty()) {now=Q.top();//队首元素Q.pop();//少了这句导致死循环ans[dd++]=now;for(int j=head[now]; j!=-1; j=edge[j].next) {int v=edge[j].v;indegree[v]--;if(!indegree[v])        Q.push(v);}
//		printf("%%%%%%%%%%\n");}
}int main() {int t;scanf("%d",&t);while(t--) {int n,m;scanf("%d%d",&n,&m);init();//初始化邻接表while(m--) {int a,b;scanf("%d%d",&a,&b);addedge(a,b);indegree[a]++;//目的是反向拓扑的计算}TopoSort(n);
//		printf("*******\n");for(int j=n-1; j>0; j--)      printf("%d ",ans[j]);printf("%d\n",ans[0]);}return 0;
}



vector 容器的讲解>>>>>博客园

代码实现2:容器+优先队列

参考CSDN

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
const int MYDD=1103;
const int MAXDD=1e5;
using namespace std;int edgenum;//边的标号
int head[MAXDD];//节点"头指针"
int indegree[MAXDD];//节点入度数
void init() {edgenum=0;memset(head,-1,sizeof(head));memset(indegree,0,sizeof(indegree));
}struct EDGE {int u,v,w,next;
} edge[MAXDD*2];
void addedge(int u,int v,int w) {EDGE T= {u,v,w,head[u]};edge[edgenum]=T;head[u]=edgenum++;
}vector<int> V;//构造容器
void Topo(int x) {V.clear();//清空容器priority_queue<int> Q;//定义优先队列while(!Q.empty())	Q.pop();//清空队列for(int j=1; j<=x; j++)if(indegree[j]==0)	Q.push(j);while(!Q.empty()) {int now=Q.top();Q.pop();for(int j=head[now]; j!=-1; j=edge[j].next) {int temp=edge[j].v;indegree[temp]--;if(indegree[temp]==0)		Q.push(temp);}V.push_back(now);//容器尾部插入数字}
}int main() {int t;scanf("%d",&t);while(t--) {init();int n,m;scanf("%d%d",&n,&m);while(m--) {int a,b;scanf("%d%d",&a,&b);addedge(b,a,1);//键入反了(其实也就是反向拓扑),看了好久 indegree[a]++;}Topo(n);for(int j=n-1; j>=1; j--)	printf("%d ",V[j]);printf("%d\n",V[0]);}return 0;
}

后:

****************************


这篇关于HDU 4857 逃生(拓扑排序,优先队列,容器)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/489802

相关文章

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<