菜肴制作
题目大意
有N道菜,M个限制条件(第I道菜在第J道菜前做)。
求编号小的菜先做的最优解。
算法
拓扑
我们可以发现求字典序最小不一定是最优解。
所以我们可以建一个反图然后求字典序最大(大的往后了小的就往前了)
代码
#include <cstdio> #include <memory.h> #include <queue> struct edge{ int to,nxt; }e[300000]; int head[200000],cnt,ine[200000]; void add(int u,int v){ e[++cnt]=(edge){v,head[u]}; head[u]=cnt; ine[v]++; } int ans[200000]; int main(){ int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); memset(ine,0,sizeof(ine)); cnt=0; for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(v,u); } std::priority_queue<int> q; for(int i=1;i<=n;i++) if(!ine[i]) q.push(i); int c=0; while(!q.empty()){ int x=q.top(); q.pop(); ans[++c]=x; for(int i=head[x];i!=-1;i=e[i].nxt){ ine[e[i].to]--; if(!ine[e[i].to]) q.push(e[i].to); } } if(c<n){ printf("Impossible!\n"); }else{ for(int i=n;i>=1;i--) printf("%d ",ans[i]); printf("\n"); } } return 0; }