打卡信奥刷题（2714）用C++实现信奥题 P3243 [HNOI2015] 菜肴制作

P3243 [HNOI2015] 菜肴制作

题目描述

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

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

现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A 能尽量先吃到质量高的菜肴：

也就是说，

1. 在满足所有限制的前提下，111号菜肴尽量优先制作。

2. 在满足所有限制，111号菜肴尽量优先制作的前提下，222号菜肴尽量优先制作。

3. 在满足所有限制，111号和222号菜肴尽量优先的前提下，333号菜肴尽量优先制作。

4. 在满足所有限制，111号和222号和333号菜肴尽量优先的前提下，444号菜肴尽量优先制作。

5. 以此类推。

例 1：共444道菜肴，两条限制(3,1)(3,1)(3,1)、(4,1)(4,1)(4,1)，那么制作顺序是3,4,1,23,4,1,23,4,1,2。

例 2：共555道菜肴，两条限制(5,2)(5,2)(5,2)、(4,3)(4,3)(4,3)，那么制作顺序是1,5,2,4,31,5,2,4,31,5,2,4,3。

例 1 里，首先考虑111，因为有限制(3,1)(3,1)(3,1)和(4,1)(4,1)(4,1)，所以只有制作完333和444后才能制作111，而根据 3，333号又应尽量比444号优先，所以当前可确定前三道菜的制作顺序是3,4,13,4,13,4,1；接下来考虑222，确定最终的制作顺序是3,4,1,23,4,1,23,4,1,2。

例222里，首先制作111是不违背限制的；接下来考虑222时有(5,2)(5,2)(5,2)的限制，所以接下来先制作555再制作222；接下来考虑333时有(4,3)(4,3)(4,3)的限制，所以接下来先制作444再制作333，从而最终的顺序是1,5,2,4,31,5,2,4,31,5,2,4,3。现在你需要求出这个最优的菜肴制作顺序。无解输出Impossible!（首字母大写，其余字母小写）

输入格式

第一行是一个正整数ttt，表示数据组数。接下来是ttt组数据。对于每组数据：第一行两个用空格分开的正整数nnn和mmm，分别表示菜肴数目和制作顺序限制的条目数。接下来mmm行，每行两个正整数x,yx,yx,y，表示xxx号菜肴必须先于yyy号菜肴制作的限制。

输出格式

输出文件仅包含ttt行，每行nnn个整数，表示最优的菜肴制作顺序，或者Impossible!表示无解。

输入输出样例 #1

输入 #1

3 5 4 5 4 5 3 4 2 3 2 3 3 1 2 2 3 3 1 5 2 5 2 4 3

输出 #1

1 5 3 4 2 Impossible! 1 5 2 4 3

说明/提示

【样例解释】

第二组数据同时要求菜肴111先于菜肴222制作，菜肴222先于菜肴333制作，菜肴333先于菜肴111制作，而这是无论如何也不可能满足的，从而导致无解。

【数据范围】

100%100\%100%的数据满足n,m≤105n,m\le 10^5n,m≤105，1≤t≤31\le t\le 31≤t≤3。

mmm条限制中可能存在完全相同的限制。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intt,n,m,x,y,cnt;intin[N],ans[N];vector<int>vec[N];priority_queue<int,vector<int>,less<int>>que;//也可以写成默认状态priority_queue<int>que;intmain(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>t;while(t--){cin>>n>>m;cnt=0;for(inti=1;i<=n;i++)ans[i]=in[i]=0;for(inti=1;i<=n;i++)vec[i].clear();//多测不清空，十年OI一场空for(inti=1;i<=m;i++){cin>>x>>y;in[x]++;vec[y].push_back(x);//反向建边}for(inti=1;i<=n;i++)if(!in[i])que.push(i);while(!que.empty()){intu=que.top();//优先队列打乱了原序，所以只能用top，而不能用front！！！que.pop();for(inti=0;i<vec[u].size();i++){intx=vec[u][i];in[x]--;//解放连边if(!in[x])que.push(x);}ans[++cnt]=u;//记录答案}if(cnt<n)cout<<"Impossible!";elsefor(inti=cnt;i>=1;i--)//倒着输出，原因看“算法分析”cout<<ans[i]<<" ";cout<<endl;}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容