P3243 [HNOI2015] 菜肴制作 题解
2024sdhkdj
·
2023-08-20 14:41:27
·
题解
题目传送门
这题一开始苦苦调错一上午，样例都没过，交上去只有十分，于是看了下题解以后知道了错因。可能有许多人和我错在同样的地方，以下为我自己的见解，仅供参考。
题意描述：
这题的题意很好懂，就是给定 n 菜肴和 m 个限制条件，对于每个限制条件 x 和 y ，表示 x 号菜肴必须先于 y 号菜肴。让你求出在满足最小号的菜肴尽量靠前的前提下次小号的菜肴也尽量靠前、次小号的菜肴尽量靠前的前提下次次小号的菜肴也尽量靠前。（注意不是字典序 ！！！我就是这里理解有误才至错的！！！）以此类推，最优的菜肴制作顺序。如若无解，则输出 Impossible!。
算法分析：
按照我以前的思路，按照先选的菜肴 \Rightarrow 后选的菜肴的方式建边，然后直接在上面拓扑排序，最后在判环输出即可。可这样是行不通的，不信？我们看两个例子：
第一个例子：
假设存在一组数据为：
1
6 4
5 3
3 1
6 4
4 2根据题意，可以得出如下关系：
$6 \Rightarrow 4 \Rightarrow 2$。
（我们定义一串关系为一条**链**，$5,6$ 等位于一条链首位的为**链头**，$1,2$ 等位于一条链末尾的为**链尾**，下同。）
按照我们原来的思路，拓扑排序的结果为：$531642$，乍一看确实是正确的，但还有第二组数据：
~~~
1
6 4
5 4
4 2
6 3
3 1
~~~
根据题意，可以得出如下关系：
$5 \Rightarrow 4 \Rightarrow 2$，
$6 \Rightarrow 3 \Rightarrow 1$。
可以看到，这组数据与原来的不同就是 $6$ 与 $5$ 的位置调换。如果还是按照原来的思路，则拓扑排序的结果为：$542631$，然而符合题目要求的正确答案却是 $631542$。于是可以发现，这种思路的错误之处在于我们是按照**链头**的顺序考虑的（即上边第二个样例中的 $5 < 6$ 所以误判优先删除 $5$ 号菜肴开始的关系链），而题意是根据**链尾**的顺序实现的，因此需要每一次优先考虑删除**链尾**最小的**链**。
好了，问题找到了，那么该如何实现呢？
暴力找链尾肯定是行不通的，于是我们可以反向建边，然后根据链头（原来的链尾）从大到小按次删点删边，存入 $ans$ 数组里，然后倒着输出。至于为什么倒着输出，是因为我们是反向建边，且是从大到小的顺序；而输出是正向的，从小到大的顺序。这里还有一个问题，如何排序呢？
**~~[CJT](https://www.luogu.com.cn/user/926432) 直呼优先队列大法好！！！~~**
没错，这里推荐一种很实用的 STL：优先队列。它可以自定义优先级，在入队时顺便完成排序，非常方便。想了解具体可以看这篇[博客](https://blog.csdn.net/weixin_36888577/article/details/79937886?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169250321716800185867974%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169250321716800185867974&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-79937886-null-null.142^v93^chatsearchT3_1&utm_term=%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97&spm=1018.2226.3001.4187)。
## AC 代码
~~~
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,m,x,y,cnt;
int in[N],ans[N];
vector<int> vec[N];
priority_queue<int,vector<int>,less<int> >que;//也可以写成默认状态priority_queue<int>que;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>t;
while(t--){
cin>>n>>m;
cnt=0;
for(int i=1;i<=n;i++)
ans[i]=in[i]=0;
for(int i=1;i<=n;i++)
vec[i].clear();//多测不清空，十年OI一场空
for(int i=1;i<=m;i++){
cin>>x>>y;
in[x]++;
vec[y].push_back(x);//反向建边
}
for(int i=1;i<=n;i++)
if(!in[i])
que.push(i);
while(!que.empty()){
int u=que.top();//优先队列打乱了原序，所以只能用top，而不能用front！！！
que.pop();
for(int i=0;i<vec[u].size();i++){
int x=vec[u][i];
in[x]--;//解放连边
if(!in[x])
que.push(x);
}
ans[++cnt]=u;//记录答案
}
if(cnt<n)
cout<<"Impossible!";
else
for(int i=cnt;i>=1;i--)//倒着输出，原因看“算法分析”
cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}
~~~
[AC 记录](https://www.luogu.com.cn/record/121898870)
[我的 BLOG](https://www.luogu.com.cn/blog/hsb0507/)