P3243 [HNOI2015]菜肴制作（拓扑 + 优先队列）
知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。ATM 酒店为小 A 准备了 n 道菜肴，酒店按照为菜肴预估的质量从高到低给予 1 到 n 的顺序编号，预估质量最高的菜肴编号为 1。
由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 m 条形如 iii 号菜肴必须先于 j 号菜肴制作的限制，我们将这样的限制简写为 (i,j)。
现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A 能尽量先吃到质量高的菜肴：
也就是说，
在满足所有限制的前提下，1 号菜肴尽量优先制作。
在满足所有限制，1 号菜肴尽量优先制作的前提下，2 号菜肴尽量优先制作。
在满足所有限制，1 号和 2 号菜肴尽量优先的前提下，3 号菜肴尽量优先制作。
在满足所有限制，1 号和 2 号和 3 号菜肴尽量优先的前提下，4 号菜肴尽量优先制作。
以此类推。
例 1：共 4 道菜肴，两条限制 (3,1)、(4,1)，那么制作顺序是 3,4,1,2。
例 2：共 5 道菜肴，两条限制 (5,2)、(4,3)，那么制作顺序是 1,5,2,4,3。
例 1 里，首先考虑 1，因为有限制 (3,1) 和 (4,1)，所以只有制作完 3 和 4 后才能制作 1，而根据 3，3 号又应尽量比 4 号优先，所以当前可确定前三道菜的制作顺序是 3,4,1；接下来考虑 2，确定最终的制作顺序是 3,4,1,2。
例 2 里，首先制作 1 是不违背限制的；接下来考虑 222 时有 (5,2) 的限制，所以接下来先制作 5 再制作 2；接下来考虑 3 时有 (4,3) 的限制，所以接下来先制作 4 再制作 3，从而最终的顺序是 1,5,2,4,3。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible!（首字母大写，其余字母小写）
输入格式
第一行是一个正整数 t，表示数据组数。接下来是 ttt 组数据。对于每组数据：第一行两个用空格分开的正整数 n 和 m，分别表示菜肴数目和制作顺序限制的条目数。接下来 m 行，每行两个正整数 x,y，表示 x 号菜肴必须先于 y 号菜肴制作的限制。
输出格式
输出文件仅包含 t 行，每行 n 个整数，表示最优的菜肴制作顺序，或者 Impossible! 表示无解。
输入输出样例
输入 #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
说明/提示
【样例解释】
第二组数据同时要求菜肴 1 先于菜肴 2 制作，菜肴 2 先于菜肴 3 制作，菜肴 3 先于。
菜肴 1 制作，而这是无论如何也不可能满足的，从而导致无解。
【数据范围】
100%的数据满足 n,m≤1e5，1≤t≤3。
m 条限制中可能存在完全相同的限制。
首先建图看一下：
我们可以发现规律：从上向下走，如果看成BFS，就是每次选取一层（小-->大排序，就是该层选取的最优解） 【请接着看，这个只是当时的猜测】
5 3 4 2
再看一个样例：
1 5 2 4 3
到这里，似乎可以发现是拓扑排序了！！！
那就解决80%了！
再看个样例：
发现：如果成环就输出 ：
Impossible!
这也不难理解，因为成环无法 拓扑排序
思路：因为题意是让我们优先找最小的
所以我们 可以存反图 + 优先队列（大根堆）
最后倒序输出就可以了
AC代码如下：#include <bits/stdc++.h>
#define ll long long
#define buff
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#define endl "n"
using namespace std;
const int N = 1e5 + 9;
int e[N], ne[N], h[N], idx;
int d[N];
int tuop[N], cnt;
int n, m;
priority_queue<int> q; //大根堆
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void clea()
{
// memset(e,0,sizeof e);
// memset(ne,0,sizeof ne);
// memset(h,0,sizeof h);
idx = 0;
// while (!q.empty())
// {
// q.pop();
// }
}
bool tuopsort()
{
while (!q.empty())
{
int t = q.top();
tuop[++cnt] = t;
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j]--;
if (d[j] == 0)
q.push(j);
}
}
if (cnt == n)
return 1;
else
return 0;
}
void solve()
{
clea();
cin >> n >> m;
cnt = 0;
memset(h, -1, sizeof h);
memset(d, 0, sizeof d);
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
add(b, a); //存反图
d[a]++;
}
for (int i = 1; i <= n; i++)
{
if (d[i] == 0)
q.push(i);
}
if (tuopsort() == 0)
{
cout << "Impossible!" << endl;
}
else
{
// cout<<"********"<<endl;
for (int i = cnt; i >= 1; i--)
{
cout << tuop[i] << ' ';
}
cout << endl;
}
}
int main()
{
buff int t;
cin >> t;
while (t--)
solve();
}
相关知识
植物的根系拓扑结构与生态适应.pptx
全国花样滑冰队列滑大奖赛开赛
魔芋菜肴
队列花球展风采，昂首绰约飒英姿——石门小学队列花球操比赛
土体柔韧性对结构拓扑优化的影响,International Journal for Numerical and Analytical Methods in Geomechanics
组队赛8：Journey to the “The World's Start” 二分+单调队列优化dp
鲜花菜肴
寻味藤田特色菜肴——魔芋豆腐
襄阳魔芋菜肴
花卉菜肴介绍及菜品实例.doc
网址: P3243 [HNOI2015]菜肴制作（拓扑 + 优先队列） https://m.huajiangbk.com/newsview1099039.html
| 上一篇: 【步骤图】蒜泥白肉的做法 |
下一篇: P3243 [HNOI2015] |
