Gym 100792K King’s Rout

2019-11-11 04:14:22

字体：大中小

来源：转载

供稿：网友

Gym 100792K King’s Rout

拓扑排序

传送门：HustOJ

传送门：CodeForce

题意

有编号为1~n的客人要去吃饭，然后他们会先后到达，现在已经知道了有些人一定会先于另外有些人到达，要求得到人们到达的先后次序，同时要尽量使编号小的人先到达。

思路

通过知道了有些人先于另外某些人到达，我们可以通过拓扑排序算出他们到达的先后次序。但是题目要求编号小的人尽量先到，也就是说没有强制要求的关系里面，我们要让编号小的人先到达。如果从头开始计算的话，我们发现情况很是复杂。比如第一个样例：3 1，即要求3在1 前面到达，如果我们按照拓扑排序的方法，会将2和3同时入队，这时候就造成了判断的难点，如果让2先出队，显然是错误的。但是我们如果反过来呢？也就是对于3 1，我们令3的入度变为1。拓扑排序有0入度优先，0出度优先，这题就是0出度优先，进行倒着拓扑排序，再倒着输出。这个时候，就是1和2同时入队，此时我们是可以分辨出谁应该先出队的。只要利用优先队列按照编号从小到大出队即可。

代码

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>#define _ ios_base::sync_with_stdio(0);cin.tie(0);using namespace std;const int MAXN=200005;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;vector<int> G[MAXN];PRiority_queue<int> que;int indegree[MAXN];vector<int> res;int main(){ _ int n, m; while(cin>>n) { cin>>m; int cnt=0; for(int i=0;i<MAXN;i++) G[i].clear(); while(!que.empty()) que.pop(); memset(indegree, 0, sizeof(indegree)); res.clear(); for(int i=0;i<m;i++) { int ta, tb; cin>>ta>>tb; G[tb].push_back(ta); indegree[ta]++; } for(int i=1;i<=n;i++) if(indegree[i]==0) que.push(i); while(!que.empty()) { int tt=que.top();que.pop(); res.push_back(tt); for(int i=0;i<G[tt].size();i++) if(!(--indegree[G[tt][i]])) que.push(G[tt][i]); //度变成0了就加到队列里面 } for(int i=res.size()-1;i>=0;i--) cout<<res[i]<<(i==0 ? '/n' : ' '); } //system("pause"); return 0;}

上一篇：POJ1251- Jungle Roads（Kruskal）

下一篇：2.6小记

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注