正題

題目鏈接:https://www.luogu.com.cn/problem/P3243

---

題目大意

$n$個(gè)數(shù)，有$m$個(gè)要求形如$x$在$y$的前面，現(xiàn)在要求在$i?1$盡量靠前的情況下$i$盡量靠前$(i>1)$
求這個(gè)序列

---

解題思路

這個(gè)很顯然要求是張有向圖無環(huán)圖，然后若第$i$個(gè)數(shù)排在第$x$位，那么$p_i=x$，那么就是要求$p$的字典序最小。但是發(fā)現(xiàn)如果直接拓?fù)渑判?#43;優(yōu)先隊(duì)列就會(huì)導(dǎo)致拓?fù)湫虻淖值湫蜃钚?#xff0c;不符合題意，但是如果我們將拓?fù)鋱D反過來跑就是正確答案了。

這樣子跑是保證了反過來的字典序最大，那么小的一定在后面也就是保證了反過來后$p_i$小的一定在前面。

時(shí)間復(fù)雜度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e5+10; struct node{int to,next; }a[N]; int T,n,m,tot,cnt,in[N],ls[N],top[N]; priority_queue<int> q; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;in[y]++;return; } void topsort(){for(int i=1;i<=n;i++)if(!in[i])q.push(i);while(!q.empty()){int x=q.top();top[++cnt]=x;q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;in[y]--;if(!in[y])q.push(y);}}return; } int main() {scanf("%d",&T);while(T--){tot=cnt=0;memset(ls,0,sizeof(ls));memset(in,0,sizeof(in));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(y,x);}topsort();if(cnt!=n)printf("Impossible!");else{for(int i=n;i>=1;i--)printf("%d ",top[i]);}putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3243-[HNOI2015]菜肴制作【拓扑排序,优先队列】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。