题面
https://www.luogu.org/problem/P3243
题解
(1)在满足所有限制的前提下，1号菜肴”尽量“优先制作；
(2)在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作；
(3)在满足所有限制，1号和2号菜肴”尽量“优先的前提下，3号菜肴”尽量“优先制作；
(4)在满足所有限制，1号和2号和3号菜肴”尽量“优先的前提下，4 号菜肴”尽量“优先制作；
我们可以想到字典序，但是绝对不是字典序最小。
举个反例假设$2$先于$4$，$3$先于$1$，
字典序最小是$2,3,1,4$，但是题目要求的是$3,1,2,4$。
所以求反序列的字典序最大即可。
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 100500 #define ri register int using namespace std; int n,m,ans[N],ru[N]; vector<int> to[N]; priority_queue<int> q; inline int read() { int ret=0,f=0; char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) f|=(ch==‘-‘),ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) ret*=10,ret+=(ch-‘0‘),ch=getchar(); return f?-ret:ret; } int main(){ int T=read(); while (T--) { n=read(); m=read(); for (ri i=1;i<=n;i++) to[i].clear(),ru[i]=0; for (ri i=1;i<=m;i++) { int u=read(),v=read(); to[v].push_back(u); ru[u]++; } for (ri i=1;i<=n;i++) if (!ru[i]) q.push(i); int cc=0; while (!q.empty()) { int x=q.top(); q.pop(); ans[++cc]=x; for (ri i=0;i<to[x].size();i++) { ru[to[x][i]]--; if (!ru[to[x][i]]) q.push(to[x][i]); } } if (cc!=n) { puts("Impossible!"); } else { for (ri i=n;i>=1;i--) printf("%d ",ans[i]); puts(""); } } return 0; }
原文：https://www.cnblogs.com/shxnb666/p/11297792.html