菜肴制作 计蒜客 C++

题目：

知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。

ATM 酒店为小 A 准备了 N 道菜肴，酒店按照为菜肴预估的质量从高到低给予 1 到 N 的顺序编号，预估质量最高的菜肴编号为 1。由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 M 条形如「i 号菜肴『必须』先于 j 号菜肴制作”的限制」，我们将这样的限制简写为 〈i,j〉。

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

在满足所有限制的前提下，1 号菜肴「尽量」优先制作；在满足所有限制，1 号菜肴「尽量」优先制作的前提下，2 号菜肴「尽量」优先制作；在满足所有限制，1 号和 2 号菜肴「尽量」优先的前提下，3 号菜肴「尽量」优先制作；在满足所有限制，1 号和 2 号和 3 号菜肴「尽量」优先的前提下，4 号菜肴「尽量」优先制作；以此类推。

例一：共四道菜肴，两条限制 〈3,1〉、〈4,1〉，那么制作顺序是 3,4,1,2。

例二：共五道菜肴，两条限制 〈5,2〉、〈4,3〉，那么制作顺序是 1,5,2,4,3。

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

例二里，首先制作 1 是不违背限制的；接下来考虑 2 时有 〈5,2〉 的限制，所以接下来先制作 5 再制作 2；接下来考虑 3 时有 〈4,3〉 的限制，所以接下来先制作 4 再制作 3，从而最终的顺序是 1,5,2,4,3。

现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” （不含引号，首字母大写，其余字母小写）

输入格式

第一行是一个正整数 D，表示数据组数。接下来是 D 组数据。对于每组数据：第一行两个用空格分开的正整数 N 和 M，分别表示菜肴数目和制作顺序限制的条目数。接下来 M 行，每行两个正整数 x,y，表示「x 号菜肴必须先于 y 号菜肴制作」的限制。（注意：M 条限制中可能存在完全相同的限制）

输出格式

输出文件仅包含 D 行，每行 N 个整数，表示最优的菜肴制作顺序，或者”Impossible!”表示无解（不含引号）。

数据范围和约定

对于100%的数据，N,M≤100000, D≤3。

解决思路

本题咋一看可以用拓扑排序解决，但经过观察仅用拓扑排序，无法解决拓补排序多解情况，即无法按照题目要求尽量优先吃到质量高菜肴。故可以反向思考，通过进行逆拓扑排序，字典序大的先输出，最后用reverse函数输出。注意，Impossible情况为有环存在。

这里逆拓扑需要建立出度数组，同时注意重复数据输入。可以借用c++自带的set容器和vector容器。

另外，由于数据量很大，在逆拓扑时用常规的stack或deque容器可能得不到正确答案（可以看一下测试网页上用户输出是否完全输出），可以用一个大根堆（优先级队列）解决。

c++代码：

#include <iostream>

#include <vector>

#include <queue>

#include <set>

#include <algorithm>

using namespace std;

bool topologicalSort(vector<set<int>>& graph, vector<int>& deDegree, vector<int>& result) {

priority_queue<int> q;

int count = 0;

for (int i = 1; i < deDegree.size(); i++) {

if (deDegree[i] == 0) {

q.push(i);

}

}

while (!q.empty()) {

int curr = q.top();

q.pop();

result.push_back(curr);

count++;

for (int next : graph[curr]) {

deDegree[next]--;

if (deDegree[next] == 0) {

q.push(next);

}

}

}

return count == graph.size() - 1;

}

int main() {

int D;

cin >> D;

vector<vector<int>> result(D);

vector<int> flag(D);

for (int d = 0; d < D; d++) {

int N, M;

cin >> N >> M;

vector<set<int>> graph(N + 1);

vector<set<int>> graph2(N + 1);

vector<int> deDegree(N + 1, 0);

for (int i = 0; i < M; i++) {

int from, to;

cin >> from >> to;

graph[from].insert(to);

graph2[to].insert(from);

deDegree[from] = graph[from].size();

}

if (topologicalSort(graph2, deDegree, result[d])) {

reverse(result[d].begin(), result[d].end());

flag[d] = 1;

}

}

for (int i = 0; i < D; i++) {

if (flag[i]) {

for (int num : result[i]) {

cout << num << " ";

}

}

else {

cout << "Impossible!";

}

cout << endl;

}

system("pause");

}

相关知识

蒜苔到底是不是碳水化合物（探寻蒜苔的营养成分和分类）
C++做的玫瑰花
寻味藤田特色菜肴——魔芋豆腐
尖椒蒜片西兰花的做法
菜花制作菜谱制作减肥素菜菜谱大全
魔芋菜肴
字符串 (C++/CX)
探索C++之美：玫瑰花代码项目推荐
C++控制台渲染一朵逼真的玫瑰花
魔芋美食菜肴

网址: 菜肴制作 计蒜客 C++ https://www.huajiangbk.com/newsview1098983.html