Gym 100792K King’s Rout

2019-11-11 02:16:47

字體：大中小

供稿：網(wǎng)友

Gym 100792K King’s Rout

題意

有編號(hào)為1~n的客人要去吃飯，然后他們會(huì)先后到達(dá)，現(xiàn)在已經(jīng)知道了有些人一定會(huì)先于另外有些人到達(dá)，要求得到人們到達(dá)的先后次序，同時(shí)要盡量使編號(hào)小的人先到達(dá)。

思路

通過知道了有些人先于另外某些人到達(dá)，我們可以通過拓?fù)渑判蛩愠鏊麄兊竭_(dá)的先后次序。但是題目要求編號(hào)小的人盡量先到，也就是說沒有強(qiáng)制要求的關(guān)系里面，我們要讓編號(hào)小的人先到達(dá)。如果從頭開始計(jì)算的話，我們發(fā)現(xiàn)情況很是復(fù)雜。比如第一個(gè)樣例：3 1，即要求3在1 前面到達(dá)，如果我們按照拓?fù)渑判虻姆椒ǎ瑫?huì)將2和3同時(shí)入隊(duì)，這時(shí)候就造成了判斷的難點(diǎn)，如果讓2先出隊(duì)，顯然是錯(cuò)誤的。但是我們?nèi)绻催^來呢？也就是對于3 1，我們令3的入度變?yōu)?。拓?fù)渑判蛴?入度優(yōu)先，0出度優(yōu)先，這題就是0出度優(yōu)先，進(jìn)行倒著拓?fù)渑判颍俚怪敵觥＿@個(gè)時(shí)候，就是1和2同時(shí)入隊(duì)，此時(shí)我們是可以分辨出誰應(yīng)該先出隊(duì)的。只要利用優(yōu)先隊(duì)列按照編號(hào)從小到大出隊(duì)即可。

代碼

#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了就加到隊(duì)列里面 } for(int i=res.size()-1;i>=0;i--) cout<<res[i]<<(i==0 ? '/n' : ' '); } //system("pause"); return 0;}

上一篇：【Bzoj1878】HH的項(xiàng)鏈

下一篇：系統(tǒng)廣播大全