题解 P3243 【[HNOI2015]菜肴制作】
Hexarhy
2019-01-28 23:33:00
### 这道题目是练手拓扑的好题之一。
小编的[拓扑教程](https://80049.blog.luogu.org/kuai-su-ru-shou-ta-pu-pai-xu)，欢迎来看。~~此题评为紫题会不会偏高？~~
------------
### 思路：
$1)$先考虑$Impossible$的情况。很明显，由于这是个有向图，而做菜品必定有一个是可以**直接**动手做的，这也意味，如果没有点入度为$0$，即出现了**闭环**，那么就不符题意。
> 判断环很简单，在拓扑完了的时候 看看答案数组有没有$n$个，没有证明有点入不了队，即没有点入度为$0$,出现环。
$2)$可是该怎么拓扑呢？不妨设编号小的菜为$a$，编号大的菜为$b$。我们想要$a$尽量往前靠，可是贪心很容易举出反例（看其他人题解有），这样做不好。那么换种方向，我们让$b$尽量往后靠，**不论$b$具体在哪，我们都能保证$a$在前面，因此就需要反向跑拓扑。让$b$连向$a$，跑反图的拓扑。**
> 注意：我们让编号越大，越往后靠，所以要每次队列都取最大值，因此就用大根堆（优先队列）维护。
$3)$说说坑点~~（害我调试那么久了）~~：
> 由于有多组数据，因此别忘记每次做完要清空数组。包括答案数组和下标，入度数组，邻接链表，堆等。
> 由于我们反图跑拓扑，因此答案数组存储也是反的，输出的时候记得倒序。
> 考虑到内存与时间问题，不要用邻接矩阵建图。邻接链表实现此题用$vector$会更简单（具体实现看程序大家就能懂）！
------------
一个编程时的语法问题：
`const int tmp=q.top();`与`const int& tmp=q.top();`相比，**后者**会导致一些**不可预料的错误**（我也不知道）。所以引用符&，还是别乱用。
~~求好心人告诉作者为什么。~~
------------
程序如下，请看注释：~~（作者自认为码风很好QWQ）~~
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=100005;
int n,m,cnt;//cnt是答案数组的下标
int indeg[MAXN],ans[MAXN];
vector <int> edge[MAXN];//vector建图就是方便！
void input(void)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
edge[y].push_back(x);//反向建图
indeg[x]++;
}
}
void topo_sort(void)
{
priority_queue <int> q;//大根堆，每次取最大值
for(int i=1;i<=n;i++)
if(!indeg[i])
q.push(i);//初始化一下队列
while(!q.empty())
{
const int tmp=q.top();//不要加引用符&！！！
q.pop();
ans[++cnt]=tmp;
for(vector<int>::iterator it=edge[tmp].begin();it!=edge[tmp].end();it++)//遍历边
{
indeg[*it]--;//拓扑排序
if(!indeg[*it])
q.push(*it);
}
}
}
void output(void)
{
if(cnt<n)//答案数组长度不足，有闭环，不符题意
{
puts("Impossible!");
return;
}
for(int i=n;i>=1;i--)//记得倒序输出QVQ
cout<<ans[i]<<' ';
cout<<endl;
}
void clear(void)
{
cnt=0;
memset(ans,0,sizeof(ans));
memset(indeg,0,sizeof(indeg));
for(int i=1;i<=n;i++)
edge[i].clear();
}
int main()
{
int T;
cin>>T;
while(T--)
{
clear();//清空很重要
input();
topo_sort();
output();
}
return 0;
}
```