第一眼看到這題，頓時懵逼，一個 \(SB\) 拓撲序竟然是黑題，當場笑噴。

\(Of\) \(course\)，這題我是用堆做的。（其實是優先隊列，手寫堆這么垃圾我怎么可能會用呢）

\((1)\) 首先建圖。如果 \(x\) 需要在 \(y\) 前面，就從 \(y\) 向 \(x\) 連邊。

\((2)\) 然后把沒有入邊的點先加入堆。每次從堆中取出最小的數記下來。

\((3)\) 然后把它連向的點全都入堆。直到堆空。如果取出的點不是 \(n\) 個就輸出不可能。否則輸出記下來的點就好了。

#include<cstdio> #include<cstring> #include<queue> using namespace std; const int MAX_N=100010; struct EDGE{int v,nxt; }e[MAX_N]; int d,n,m,in[MAX_N],cnt,head[MAX_N],a[MAX_N]; priority_queue<int> q; inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } void add(int u,int v){e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt; } bool bfs(){while(!q.empty()){int p=q.top();q.pop();cnt++;a[cnt]=p;for(int i=head[p];i;i=e[i].nxt){int v=e[i].v;in[v]--;if(!in[v]){q.push(v);}}}return cnt==n; } int main(){d=read();while(d--){memset(in,0,sizeof(in));memset(head,0,sizeof(head));cnt=0;n=read(),m=read();for(int i=1;i<=m;i++){int x,y;x=read(),y=read();add(y,x);in[x]++;}for(int i=1;i<=n;i++){if(!in[i]){q.push(i);}}cnt=0;if(bfs()){for(int i=n;i>=1;i--){printf("%d ",a[i]);}printf("\n");}else{printf("Impossible!\n");}}return 0; } /* 3 5 4 5 4 5 3 4 2 3 2 3 3 1 2 2 3 3 1 5 2 5 2 4 3 1 5 3 4 2 Impossible! 1 5 2 4 3 */

轉載于:https://www.cnblogs.com/errichto/p/11317983.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的洛谷 P3243 【[HNOI2015]菜肴制作】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。