解析

很好的題
也就是我沒做出來的意思
反向思維似乎是我欠缺的
這道題也是
也許做題時應該多特意往這邊想想
當正向看并沒有太好的性質時，也許反過來能使題目豁然開朗

容易想到暴力n方如何做
（以下均指反圖）
找到1所在的點，染色找到其導出的子圖，在其中再找到最小的點，再求導出圖…直到子圖大小為1時，把結點放到當前答案序列的開頭

那么不難發現，每個點導出的子圖都是占據答案序列上連續的一段，同時最小的結點會在這一段的最后

然后…我就發現不出來了…

考慮反過來想
答案序列最后一個點，必然是入度為0的編號最大的點
因為它永遠不會被其他點的導出子圖選中，并且會被貪心的在全部圖中最后一個選到
而且，去掉這個點和相關的邊后，剩下的圖依然滿足這個性質！
所以就得到了本題的策略：在反圖上跑字典序最大的拓撲即可
代碼實現上，把隊列改稱大根堆即可

代碼

#include<bits/stdc++.h>const int N=1e5+100; const int M=2e3+100; const int mod=1e9+7; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int key=13331;int n,m,Q; struct node{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; } int du[N],ans[N],num; priority_queue<int>q;void init(){memset(fi,-1,sizeof(fi));cnt=-1;memset(du,0,sizeof(du));num=0; } int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifint T=read();while(T--){init();n=read();m=read();for(int i=1;i<=m;i++){int x=read(),y=read();addline(y,x);du[x]++;}for(int i=1;i<=n;i++){if(!du[i]) q.push(i);}while(!q.empty()){int now=q.top();q.pop();ans[++num]=now;for(int i=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(--du[to]==0){q.push(to);}}}if(num!=n) printf("Impossible!\n");else{for(int i=n;i>=1;i--) printf("%d ",ans[i]);putchar('\n');}}return 0; } /*5 37 1 4 1 9 1 3 5 31 1 4 22 3 5 */

總結

以上是生活随笔為你收集整理的P3243 [HNOI2015]菜肴制作（拓扑排序、贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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