「Machine Schedule」机器任务

形式化题目

有两台机器 $A$ 、 $B$ ， $A$ 有 $N$ 种模式 $0 \sim N-1$ ， $B$ 有 $M$ 种模式 $0 \sim M-1$ ，初始都停在模式 $0$ 。给定 $K$ 个任务，任务 $i$ 交给 $A$ 做要求 $A$ 处于模式 $a_i$ ，交给 $B$ 做要求 $B$ 处于模式 $b_i$ ；每个任务必须且只能由一台机器完成。

任务可以按任意顺序执行。一台机器每切换一次模式记一次重启，求完成全部任务所需的最少重启次数。

约束： $N, M < 100$ ， $K < 1000$ ， $0 \leqslant a_i < N$ ， $0 \leqslant b_i < M$ ，多组数据。

正解

思路

朴素做法：枚举每个任务分给 $A$ 还是 $B$ ，再枚举执行顺序。分配方案有 $2^K$ 种， $K < 1000$ 时完全不可行；而且这个做法看不出题目真正的结构。

关键观察：顺序其实是无关变量。 对一台机器来说，重要的是"它最终要经过哪些模式"。若分配给 $A$ 的任务需要的模式集合是 $S_A$ ，那么 $A$ 的最少重启次数就是 $|S_A \setminus \{0\}|$ ：从初始模式 $0$ 出发，依次切到每个新模式恰好一次即可，重复访问某个模式不会更省。于是顺序被彻底消掉，问题只剩"选哪些模式"。

坑点：模式 $0$ 是免费的，必须删掉。 若 $a_i = 0$ ，这个任务交给 $A$ 时 $A$ 根本不用动（初始就在模式 $0$ ），它不强迫我们新增任何模式，也不产生代价。所以 $a_i = 0$ 或 $b_i = 0$ 的任务可以直接删除。若把它当普通边建进图里，最优解就被迫去覆盖那个本不需要付费的"模式 $0$ "点，答案一定偏大，而且偏大的量并不固定（后文图示解析给出对照）。

化为最小点覆盖。 删掉免费任务后，把所有"要付钱的模式"建成点：

左部点： $A$ 的模式 $1, 2, \dots, N-1$ ；
右部点： $B$ 的模式 $1, 2, \dots, M-1$ ；
剩下每个任务 $i$ 连一条无向边 $(a_i, b_i)$ 。

选哪些模式就是"选图中的哪些点"，代价是选中点数；而"每个任务至少被一台机器覆盖" 就是"每条边至少有一个端点被选中"——这正是点覆盖的定义。度为 $0$ 的模式永远不会被最优解选中，忽略它们不改变结论。所以

\text{答案} = \text{二分图的最小点覆盖大小}

König 定理。 图是二分图（左侧只有 $A$ 的模式，右侧只有 $B$ 的模式），由 König 定理：二分图最小点覆盖大小 $=$ 最大匹配大小。于是问题变成求最大匹配。

举个例子：题面样例 $N=M=5$ ， $K=10$ 且没有 $0$ 任务，建出的二分图如下（左 $A$ 右 $B$ ）。

graph LR
    subgraph LA["A 的模式（左部）"]
        direction TB
        A1["1"]
        A2["2"]
        A3["3"]
        A4["4"]
    end
    subgraph RB["B 的模式（右部）"]
        direction TB
        B1["1"]
        B2["2"]
        B3["3"]
        B4["4"]
    end
    A1 --- B1
    A1 --- B2
    A1 --- B3
    A1 --- B4
    A2 --- B1
    A2 --- B2
    A2 --- B3
    A2 --- B4
    A3 --- B3
    A4 --- B3

任务的分配对应"每条边挑一个端点"，重启次数对应"被挑中的点数"。最小的挑法是选 $A$ 的模式 $\{1, 2\}$ 覆盖前 $8$ 条边、再选 $B$ 的模式 $\{3\}$ 覆盖后 $2$ 条，一共 $3$ 次重启，与样例输出一致。图中恰好存在 $3$ 条两两不共用端点的边（例如 $(2,1), (3,3)$ 和 $(1,4)$ ），所以最大匹配为 $3$ ，最小点覆盖不可能更小。

最大匹配用 Hopcroft–Karp。 每一轮先 BFS 给左部点分层并求出最短增广路的长度，再沿分层方向一次性把所有这么长的增广路都增广掉。每轮至少消掉一层，最多 $O(\sqrt V)$ 轮，总复杂度 $O(E\sqrt V)$ 。本题规模很小（ $V < 200$ ， $E < 1000$ ），朴素的匈牙利算法 $O(VE)$ 同样能过，选 Hopcroft–Karp 只是渐近界更稳。

代码

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
106
107
108
109
110
111
112
113
114
115
116/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 任务安排：Hopcroft-Karp 二分图最大匹配（多组数据，读到 0 结束）
#include <cstdio>
#include <vector>
using namespace std;

const int INF = 1 << 30;

int n, right_size;
vector<vector<int> > adj;
vector<int> match_l, match_r, dist;

// 给左部点分层，返回最短增广路的边数；没有增广路时返回 INF
int shortest_augmenting_length() {
    vector<int> q;
    for (int u = 0; u < n; u++) {
        bool free_l = match_l[u] < 0;
        dist[u] = free_l ? 0 : INF;
        if (free_l) {
            q.push_back(u);
        }
    }
    int shortest = INF;
    for (int h = 0; h < (int)q.size(); h++) {
        int u = q[h];
        if (dist[u] >= shortest) {
            continue;
        }
        for (int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i];
            int nx = match_r[v];
            if (nx < 0) {
                shortest = dist[u] + 1;
            } else if (dist[nx] == INF) {
                dist[nx] = dist[u] + 1;
                q.push_back(nx);
            }
        }
    }
    return shortest;
}

// 从已分层的左部点 u 出发找长度恰为 shortest 的增广路，成功就翻转匹配
bool try_augment(int u, int shortest) {
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i];
        int nx = match_r[v];
        bool grown;
        if (nx < 0) {
            grown = (dist[u] + 1 == shortest);
        } else {
            grown = (dist[nx] == dist[u] + 1) && try_augment(nx, shortest);
        }
        if (grown) {
            match_l[u] = v;
            match_r[v] = u;
            return true;
        }
    }
    dist[u] = INF; // 这个点往下到不了自由右部点，本轮放弃它
    return false;
}

int max_matching() {
    int total = 0;
    while (true) {
        int shortest = shortest_augmenting_length();
        if (shortest == INF) {
            return total;
        }
        for (int u = 0; u < n; u++) {
            if (match_l[u] < 0 && try_augment(u, shortest)) {
                total++;
            }
        }
    }
}

int main() {
    int printed = 0;
    while (true) {
        if (scanf("%d", &n) != 1) {
            break;
        }
        if (n == 0) {
            break;
        }
        int m, k;
        scanf("%d %d", &m, &k);
        adj.assign(n, vector<int>());
        for (int i = 0; i < k; i++) {
            int task, a, b;
            scanf("%d %d %d", &task, &a, &b);
            if (a && b) { // 用初始模式就能做的任务不产生约束
                adj[a].push_back(b);
            }
        }
        right_size = m;
        match_l.assign(n, -1);
        match_r.assign(m, -1);
        dist.assign(n, INF);
        printf("%d\n", max_matching());
        printed++;
    }
    if (printed == 0) {
        printf("\n");
    }
    return 0;
}

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 01:34
# update_at: 2026-10-02 01:42

import sys
from collections import deque

INF = 1 << 30  # 层号哨兵：比任何合法层号都大，表示"这个点还没被 BFS 访问到"


def shortest_augmenting_length(adj: list[list[int]], match_l: list[int],
                               match_r: list[int], dist: list[int]) -> int:
    """给左部点分层，返回最短增广路的边数；一条增广路都没有时返回 INF。

    从每个未匹配左部点出发，沿"未匹配边 → 匹配边"交替走：走到右部点 v 后，
    下一步只能沿 v 的匹配边回到 match_r[v]，所以层号只需记在左部点上。
    BFS 第一次碰到未匹配右部点得到的层数就是最短增广路长度。
    """
    queue = deque()
    for u in range(len(adj)):
        free = match_l[u] < 0          # 未匹配的左部点才是增广路起点
        dist[u] = 0 if free else INF
        if free:
            queue.append(u)
    shortest = INF
    while queue:
        u = queue.popleft()
        if dist[u] >= shortest:        # 同层及更深的点只会给出不更短的路，剪掉
            continue
        for v in adj[u]:
            nxt = match_r[v]
            if nxt < 0:                # 右部点空闲：找到一条增广路
                shortest = dist[u] + 1
            elif dist[nxt] == INF:     # 已匹配右部点：顺着它的匹配边走到左部点 nxt
                dist[nxt] = dist[u] + 1
                queue.append(nxt)
    return shortest


def try_augment(u: int, adj: list[list[int]], match_l: list[int], match_r: list[int],
                dist: list[int], shortest: int) -> bool:
    """从已分层的左部点 u 出发找一条长度恰为 shortest 的增广路，成功就翻转匹配。

    只沿分层方向 dist + 1 往下走，所以递归深度不超过层数（< N），无需放开递归上限。
    """
    for v in adj[u]:
        nxt = match_r[v]
        if nxt < 0:
            grown = dist[u] + 1 == shortest        # 只有最短增广路才在本轮使用
        else:
            grown = dist[nxt] == dist[u] + 1 and try_augment(
                nxt, adj, match_l, match_r, dist, shortest)
        if grown:
            match_l[u], match_r[v] = v, u
            return True
    dist[u] = INF             # 这个点往下到不了自由右部点，本轮放弃它
    return False


def max_matching(adj: list[list[int]], right_size: int) -> int:
    """Hopcroft–Karp：反复"分层 + 沿最短增广路批量增广"，直到不存在增广路。

    每轮把这一层能用的增广路一次用完，所以最多 O(√V) 轮；由增广路定理，
    不存在增广路时的匹配就是最大匹配。
    """
    match_l = [-1] * len(adj)      # 左部点的匹配对象，-1 表示未匹配
    match_r = [-1] * right_size    # 右部点的匹配对象，-1 表示未匹配
    dist = [INF] * len(adj)
    total = 0
    while True:
        shortest = shortest_augmenting_length(adj, match_l, match_r, dist)
        if shortest == INF:
            return total
        total += sum(try_augment(u, adj, match_l, match_r, dist, shortest)
                     for u in range(len(adj)) if match_l[u] < 0)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    for n in data:                 # 终止行只有一个 0，它落在 N 的位置上
        if n == 0:
            break
        m, k = next(data), next(data)

        # 模式 0 是初始状态：用它执行的任务不需要重启，不产生任何约束，
        # 因此只把 a[i] != 0 且 b[i] != 0 的任务建成二分图的边。
        adj: list[list[int]] = [[] for _ in range(n)]
        for _ in range(k):
            _i, a, b = next(data), next(data), next(data)  # 任务编号只作标识，不参与计算
            if a and b:
                adj[a].append(b)

        out.append(str(max_matching(adj, m)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：Hopcroft–Karp 为 $O(E\sqrt V)$ ，其中 $E \leqslant K < 1000$ 、 $V \leqslant N + M < 200$ ，单组数据在 $10^4$ 量级，多组数据也能在 1000ms 内轻松跑完。
空间复杂度： $O(V + E)$ ，即邻接表与匹配、层号数组。

总结

本题的推导是一条直线：先证明执行顺序无关（一台机器的代价只等于它需要的非 $0$ 模式数）， 再删掉两台机器都能在初始模式下完成的任务，然后把"每个任务至少被一台机器覆盖" 翻译成二分图的点覆盖，最后由 König 定理转成最大匹配。之所以能转得这么干净，关键在于模式 $0$ 是初始状态：它不需要重启，所以它对应的任务不产生任何约束—— 这一步漏掉答案就会偏大。求最大匹配用 Hopcroft–Karp， $O(E\sqrt V)$ 完成。

图示解析

样例的最优分配

下表逐任务展示上图中一组最优选点；"说明"列写出该任务是被哪台机器的哪个模式覆盖的。（这些数字是把样例输入跑一遍最大匹配 + König 构造得到的，不是手写的。）

任务 $i$	$a_i$	$b_i$	分配给谁	说明
0	1	1	A	A 选模式 1
1	1	2	A	A 选模式 1
2	1	3	A	A 选模式 1
3	1	4	A	A 选模式 1
4	2	1	A	A 选模式 2
5	2	2	A	A 选模式 2
6	2	3	A	A 选模式 2
7	2	4	A	A 选模式 2
8	3	3	B	B 选模式 3
9	4	3	B	B 选模式 3

选中的非 $0$ 模式一共 $2 + 1 = 3$ 个： $A$ 从模式 $0$ 依次切到模式 $1$ 、模式 $2$ （ $2$ 次重启）； $B$ 从模式 $0$ 切到模式 $3$ （ $1$ 次重启），共 $3$ 次。任务 $8, 9$ 交给 $B$ 后， $A$ 就不必再切到模式 $3$ 、模式 $4$ ，省下了重启。

为什么模式 0 必须排除

把这个坑拆开看：下面两个输入仅在"是否把 0 当普通模式建边"这一点上有差别。

输入	正确做法（删除 0 任务）	错误做法（把 0 当普通模式建边）
`3 3 3` / `0 0 1` / `1 1 0` / `2 2 2`	1	3
题面样例（无 0 任务）	3	3（无 0 边，两者相同）

第一行说明偏大量并不固定为 $1$ ：正确做法只需选 $B$ 的模式 $2$ （ $1$ 次重启）；而错误做法把模式 $0$ 也当成一个必须被覆盖的点，任务 $(0,1)$ 与 $(1,0)$ 又各自逼出一个额外选点，于是一路涨到 $3$ 。

根源是模式 $0$ 不需要任何重启：它根本不该作为图的顶点参与点覆盖。把 $a_i = 0$ 或 $b_i = 0$ 的任务直接丢弃即可——这种任务交给对应机器时，该机器已经在模式 $0$ 上，不产生任何约束。

这个坑在本题的评测数据上会真实扣分：10 个数据文件共 19 个测试组，其中 15 组会因为把 0 当普通模式而偏大（各偏大 $1$ ）。按正确做法提交后，全部 10 个数据文件的输出均与标准答案逐行一致。