[HNOI2015] 菜肴制作

GitHub 跳转原题关系图返回列表

把限制反向建图，用大根堆在反图上做拓扑排序，再把得到的序列倒过来输出，就能得到题目要求的最优顺序。

OJ: luogu

题目 ID: P3243

难度:提高+/省选-

标签:图论拓扑排序贪心堆

日期: 2026-06-19 23:49

题意

给出若干道菜以及一些先后限制 (u, v)，表示菜 u 必须在菜 v 之前制作。

现在要在满足所有限制的前提下，找出一个“最优”的制作顺序。这里的“最优”不是普通的字典序最小，而是：

先让 1 号菜尽量早
在此基础上让 2 号菜尽量早
再在前面都最优的基础上让 3 号菜尽量早
依此类推

如果无解，就输出 Impossible!。

样例图

这张图展示第三组样例中的限制关系：

digraph G {
  rankdir=LR;
  5 -> 2;
  4 -> 3;
}

如果只看普通的“当前可选编号最小”，会得到 1 4 3 5 2，这不是题目想要的答案。题目真正想要的是先尽量让 1 靠前，再尽量让 2 靠前，所以正确顺序是 1 5 2 4 3。这说明它不是普通的最小字典序拓扑序。

思路

先看一个小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;

int T;
int n, m;
vector<int> graph[MAXN];
int indeg[MAXN];
bool used[MAXN];
int cur_order[MAXN], best_order[MAXN];
int best_pos[MAXN];
bool found;

bool better_than_best() {
    int cur_pos[MAXN];
    for (int i = 1; i <= n; i++) {
        cur_pos[cur_order[i]] = i;
    }

    if (!found) {
        return true;
    }

    for (int x = 1; x <= n; x++) {
        if (cur_pos[x] != best_pos[x]) {
            return cur_pos[x] < best_pos[x];
        }
    }
    return false;
}

// 直接枚举所有拓扑序，然后按题目要求比较哪个更优。
void dfs(int dep) {
    if (dep > n) {
        if (better_than_best()) {
            found = true;
            for (int i = 1; i <= n; i++) {
                best_order[i] = cur_order[i];
                best_pos[cur_order[i]] = i;
            }
        }
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (used[i] || indeg[i] != 0) {
            continue;
        }

        used[i] = true;
        cur_order[dep] = i;
        for (int v : graph[i]) {
            indeg[v]--;
        }

        dfs(dep + 1);

        for (int v : graph[i]) {
            indeg[v]++;
        }
        used[i] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> m;

        for (int i = 1; i <= n; i++) {
            graph[i].clear();
            indeg[i] = 0;
            used[i] = false;
        }

        for (int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            indeg[v]++;
        }

        found = false;
        dfs(1);

        if (!found) {
            cout << "Impossible!\n";
        } else {
            for (int i = 1; i <= n; i++) {
                if (i > 1) {
                    cout << ' ';
                }
                cout << best_order[i];
            }
            cout << '\n';
        }
    }

    return 0;
}

暴力会枚举所有拓扑序，然后按照题目给出的比较规则选最优的那个：

先比较 1 的位置
若相同，再比较 2 的位置
继续往后比

这个方法可以帮助理解题意，但正解不能真的枚举所有拓扑序。

关键观察是：

题目要求“小编号尽量早”，等价于反过来说：

在还没确定前面位置时，应该尽量把“大编号且当前不影响别人”的点放到后面去

因此可以换一个角度做：

把原图限制 u -> v 反过来，建成 v -> u
在反图上做拓扑排序
每次从当前入度为 0 的点里，选编号最大的那个
最后把得到的序列整体反过来输出

为什么这样是对的？

反图里入度为 0，等价于原图里出度为 0
也就是这些点在原图里已经可以尽量往后放，不会卡住别人
此时把编号大的点优先放到后面，等价于把编号小的点尽量留在前面

于是：

反图 + 大根堆：决定“后面的位置怎么放”
最终倒序输出：得到“前面的位置怎么尽量优”

如果反图拓扑排序做不满 n 个点，说明原图有环，无解。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXM = 100005;

int T;
int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], indeg[MAXN], edge_cnt;
int ans[MAXN];

// 在反图上加一条 u -> v 的边。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
    indeg[v]++;
}

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
        indeg[i] = 0;
    }
}

bool solve_case() {
    priority_queue<int> pq; // 反图里每次优先取编号最大的点

    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            pq.push(i);
        }
    }

    int tot = 0;
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        ans[++tot] = u;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            indeg[v]--;
            if (indeg[v] == 0) {
                pq.push(v);
            }
        }
    }

    if (tot != n) {
        return false;
    }

    for (int i = n; i >= 1; i--) {
        cout << ans[i];
        if (i > 1) {
            cout << ' ';
        }
    }
    cout << '\n';
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> m;
        init_graph();

        for (int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            // 原图要求 u 在 v 前面，因此在反图上连 v -> u。
            add_edge(v, u);
        }

        if (!solve_case()) {
            cout << "Impossible!\n";
        }
    }

    return 0;
}

复杂度

设点数为 n，边数为 m。

建图 $O(n + m)$
大根堆拓扑排序 $O((n + m)\log n)$

总时间复杂度 $O((n + m)\log n)$ ，空间复杂度 $O(n + m)$ 。

总结

这题最容易误判成“字典序最小拓扑序”。真正的技巧是把视角倒过来：先决定谁应该尽量靠后，再把答案翻转回来。于是题目就落成了“反图上的大根堆拓扑排序”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P3243 [HNOI2015] 菜肴制作

题目描述

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

由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 $m$ 条形如 $i$ 号菜肴必须先于 $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$ 是不违背限制的；接下来考虑 $2$ 时有 $(5,2)$ 的限制，所以接下来先制作 $5$ 再制作 $2$ ；接下来考虑 $3$ 时有 $(4,3)$ 的限制，所以接下来先制作 $4$ 再制作 $3$ ，从而最终的顺序是 $1,5,2,4,3$ 。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible!（首字母大写，其余字母小写）

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

text

输出 #1

text

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

说明/提示

【样例解释】

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

【数据范围】

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

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

[HNOI2015] 菜肴制作

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析