P3243 [HNOI2015]菜肴制作

首先，有做菜的先后顺序，是一个拓扑排序 题目用了一大段话让你相信这是求字典序最小的排列 然而好像并不对，举个栗子： $4$种菜肴，限制为$<2,4><3,1>$ 字典序最小的排列是$2,3,1,4$，而正解应该是$3,1,2,4$ 因为编号小的要尽量靠前 ------------ 那么如何拓扑排序才是正确的呢？ 从上面的栗子可以看出，把较大的数放在尽量靠后的位置，可以使较小的数尽量靠前 所以转换一个角度 建出反图，求出字典序最大的拓扑序，这样较大的数在靠前的位置 反过来输出就是要求的答案了。 别忘了$Impossible$ ``` #include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<algorithm> #define reg register #define reset(a) memset(a,0,sizeof(a)) using namespace std; const int N=1e5+5; struct node { int to,nxt; }edge[N]; int T,n,m,num,cnt,head[N],d[N],ans[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; } inline void topsort() { priority_queue<int>q; for (reg int i=1;i<=n;i++) if (!d[i]) q.push(i); while (!q.empty()) { int u=q.top(); q.pop(); ans[cnt--]=u; for (reg int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if (!--d[v]) q.push(v); } } } int main() { T=read(); while (T--) { n=read(),m=read(); num=0; reset(ans); reset(head); reset(edge); reset(d); cnt=n; for (reg int i=1;i<=m;i++) { int x=read(),y=read(); add_edge(y,x); ++d[x]; } topsort(); if (cnt) puts("Impossible!"); else { for (reg int i=1;i<=n;i++) printf("%d ",ans[i]); putchar(10); } } return 0; } ```