完美的牛栏

形式化题目

给定一个二分图 $G = (U, V, E)$ ，其中左部点集为 $U = \{1, 2, \dots, N\}$ ，右部点集为 $V = \{1, 2, \dots, M\}$ 。

每条边 $(u, v) \in E$ （ $u \in U, v \in V$ ）表示节点 $u$ 与节点 $v$ 之间存在一条连边。

求图 $G$ 的一个最大匹配 $M^*$ ，即在 $E$ 中选取最大数量的边子集，使得选出的任意两条边均没有公共端点。输出 $|M^*|$ 的值。

正解

思路

本题是经典的二分图最大匹配问题。

模型映射：
- 将每头奶牛视为左部节点 $u \in [1, N]$ ；
- 将每个牛栏视为右部节点 $v \in [1, M]$ ；
- 奶牛 $u$ 愿意去牛栏 $v$ ，等价于在 $u$ 与 $v$ 之间连接一条边 $(u, v)$ ；
- 每头奶牛只能在一个牛栏中产奶，且每个牛栏只能容纳一头奶牛，正好对应二分图匹配中“任意两条匹配边不共享端点”的约束。
算法选择（匈牙利算法）：
- 算法的核心思想是寻找增广路。
- 依次遍历每头奶牛 $u \in [1, N]$ ，尝试为其寻找一个可用牛栏：
  - 枚举 $u$ 喜欢的牛栏 $v$ ：
    - 若本轮搜索中 $v$ 尚未访问过，标记 $v$ 为已访问。
    - 如果牛栏 $v$ 尚未被分配，则直接将 $v$ 分配给 $u$ ；
    - 如果牛栏 $v$ 已被奶牛 $u' = \text{match}[v]$ 占用，则递归尝试让 $u'$ 腾挪去其喜欢的其它牛栏：
      - 若 $u'$ 成功腾挪出新的空位，则牛栏 $v$ 就可以腾出来重新分配给 $u$ 。
  - 若能成功建立或腾挪出匹配，则当前匹配总数加 1。
样例匹配过程可视化：

以样例为例， $N = 5, M = 5$ ：

奶牛 1 喜欢牛栏：2, 5
奶牛 2 喜欢牛栏：2, 3, 4
奶牛 3 喜欢牛栏：1, 5
奶牛 4 喜欢牛栏：1, 2, 5
奶牛 5 喜欢牛栏：2

增广匹配过程如下：

graph LR
    subgraph 奶牛 (左部点)
        C1[牛 1]
        C2[牛 2]
        C3[牛 3]
        C4[牛 4]
        C5[牛 5]
    end
    subgraph 牛栏 (右部点)
        S1((栏 1))
        S2((栏 2))
        S3((栏 3))
        S4((栏 4))
        S5((栏 5))
    end

    C1 ==> S2
    C2 ==> S3
    C3 ==> S1
    C4 ==> S5
    C5 -. 无法腾挪 .-> S2

牛 1 匹配栏 2；
牛 2 尝试栏 2（已被牛 1 占用，牛 1 成功腾挪至栏 5），故牛 1 改配栏 5，牛 2 配栏 2（后牛 2 亦可直接配栏 3）；
最终最多可匹配 4 头奶牛（例如牛 1 配栏 5、牛 2 配栏 3、牛 3 配栏 1、牛 4 配栏 2）。

代码

Python 版：

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#!/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-05-22 19:17
# update_at: 2026-05-22 19:17

import sys

NO_MATCH = 0  # 牛栏未匹配哨兵编号


def find_path(cow: int, adj: list[list[int]], match: list[int], visited: list[bool]) -> bool:
    """用 DFS 寻找增广路：尝试为奶牛 cow 分配牛栏。"""
    for stall in adj[cow]:
        if visited[stall]:
            continue
        visited[stall] = True
        # 若牛栏未被占用，或占用该牛栏的牛能腾挪到其它牛栏，则匹配成功
        if match[stall] == NO_MATCH or find_path(match[stall], adj, match, visited):
            match[stall] = cow
            return True
    return False


def max_bipartite_matching(n: int, m: int, adj: list[list[int]]) -> int:
    """使用匈牙利算法求解二分图最大匹配数。"""
    match = [NO_MATCH] * (m + 1)
    ans = 0
    for cow in range(1, n + 1):
        visited = [False] * (m + 1)
        if find_path(cow, adj, match, visited):
            ans += 1
    return ans


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    data = iter(tokens)
    n = int(next(data))
    m = int(next(data))

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for cow in range(1, n + 1):
        cnt = int(next(data))
        adj[cow] = [int(next(data)) for _ in range(cnt)]

    print(max_bipartite_matching(n, m, adj))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 10:43
 * update_at: 2026-10-06 10:43
 */
// main.cpp：完美的牛栏，二分图最大匹配，匈牙利算法（DFS 增广路）。
// 奶牛为左部点，牛栏为右部点；每个牛栏只容纳一头牛，即求最大匹配数。

#include <cstdio>

typedef long long ll;

const int MAXN = 205; // 最多奶牛数
const int MAXM = 205; // 最多牛栏数

int n, m; // n 头奶牛，m 个牛栏
// 邻接表（链式前向星）：edge_from 不需要，只存边指向的牛栏
int head[MAXN]; // head[cow] = 奶牛 cow 的第一条边编号
int nxt[MAXN * MAXM]; // 同一头奶牛的下一条边编号
int to[MAXN * MAXM];  // 该边指向的牛栏编号
int edge_cnt = 0;     // 边计数器

int match_stall[MAXM]; // match_stall[v] = 占用牛栏 v 的奶牛编号，0 表示空闲
bool visited[MAXM];    // visited[v] = 本轮增广中牛栏 v 是否被访问过

// 加一条边：奶牛 u 喜欢牛栏 v
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 尝试为奶牛 cow 找增广路：能找到返回 true
bool find_path(int cow) {
    // 枚举奶牛 cow 喜欢的每个牛栏
    for (int e = head[cow]; e != 0; e = nxt[e]) {
        int stall = to[e];
        if (visited[stall])
            continue; // 本轮已访问过，跳过
        visited[stall] = true;
        // 牛栏空闲，或占用它的奶牛能腾挪到其它牛栏，则匹配成功
        if (match_stall[stall] == 0 || find_path(match_stall[stall])) {
            match_stall[stall] = cow;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int s;
        scanf("%d", &s); // 第 i 头奶牛喜欢的牛栏数目
        for (int j = 1; j <= s; j++) {
            int stall;
            scanf("%d", &stall);
            add_edge(i, stall);
        }
    }

    int ans = 0; // 最大匹配数
    for (int cow = 1; cow <= n; cow++) {
        // 每轮增广前清空访问标记
        for (int v = 1; v <= m; v++)
            visited[v] = false;
        if (find_path(cow))
            ans++;
    }

    printf("%d\n", ans);
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(N \cdot M)$ 。每次为一头奶牛寻找增广路时，每个右部节点（牛栏）最多被访问一次，遍历的边数不超过总边数 $|E| \leqslant N \cdot M$ 。总共尝试 $N$ 次，故总时间复杂度为 $\mathcal{O}(N \cdot |E|) \leqslant \mathcal{O}(N \cdot M)$ 。在本题中 $N, M \leqslant 200$ ， $N \cdot M \leqslant 4 \times 10^4$ ，运行时间远小于 1000ms。
空间复杂度： $\mathcal{O}(N + M + |E|)$ 。邻接表存储图结构需要 $\mathcal{O}(N + |E|)$ 空间；匹配数组 match 和访问数组 visited 需要 $\mathcal{O}(M)$ 空间；递归栈深度最大为 $\mathcal{O}(N)$ 。空间占用极小，远低于 128MB。

总结

题目本质是标准的二分图最大匹配问题，两边分别为奶牛与牛栏。
匈牙利算法通过 DFS 寻找交替增广路，结构简洁，逻辑自然（“名花有主时尝试让原主另寻新欢”），非常适合在规模较小时（节点数数百以内）快速求解最大匹配问题。

目录

形式化题目

正解

思路

代码

复杂度

总结