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小記