luogu3243 [HNOI2015]菜肴制作

luogu3243 [HNOI2015]菜肴制作

​​ 题目描述

知名美食家小 A被邀请至ATM 大酒店，为其品评菜肴。 ATM 酒店为小 A 准备了 N 道菜肴，酒店按照为菜肴预估的质量从高到低给予1到N的顺序编号，预估质量最高的菜肴编号为1。

由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 M 条形如”i 号菜肴’必须’先于 j 号菜肴制作“的限制，我们将这样的限制简写为

#include #include #include #include #define N 110000using namespace std;priority_queueq;int num,tmp[N],n,m,h[N],a[N],nn;struct node{ int x,y,next,z;}data[N];void insert1(int x,int y){ data[++num].x=x;data[num].y=y;data[num].next=h[x];h[x]=num; tmp[y]+=1;}bool sort1(){ for (int i=1;i<=n;++i) if (tmp[i]==0) q.push(i); int num1=0; while (!q.empty()){ a[++num1]=q-();int tt=q-();q.pop(); for (int i=h[tt];i;i=data[i].next){ int y=data[i].y; tmp[y]--;if (tmp[y]==0) q.push(y); } } if (num1!=n) return false; return true;}int main(){ //freopen("p3243.in","r",stdin); //freopen("p3243.out","w",stdout); scanf("%d",&nn); while (nn--){ memset(h,0,sizeof(h));num=0; memset(tmp,0,sizeof(tmp)); memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); for (int i=1;i<=m;++i){ int x,y; scanf("%d %d",&x,&y); insert1(y,x); } if (sort1()) for (int i=n;i>=1;--i) printf("%d ",a[i]);else printf("Impossible!"); printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。