usaco-5.4.5 奶牛的电信

形式化题目

给定无向图 $G=(V,E)$ ， $|V|=N \leqslant 100$ ， $|E|=M \leqslant 600$ ，无重边；指定两个不相邻的顶点 $c_1,c_2$ 。求最小顶点集 $S \subseteq V \setminus \{c_1,c_2\}$ ，使 $G-S$ 中 $c_1$ 与 $c_2$ 不连通；若有多组最小的 $S$ ，输出字典序最小的一组（第二行升序编号）。

坏的对象是电脑（点）：一台电脑坏了，与它相连的所有连接随之失效；连接（边）本身不会坏。因此本题求的是点意义下的 $s$ - $t$ 最小割，而不是标准的边最小割。

样例网络 $1-3-2$ （ $c_1=1,c_2=2$ ）中， $1$ 与 $2$ 之间唯一路径是 $1 \to 3 \to 2$ ，坏掉电脑 $3$ 即断开，输出 1 与 3。

正解

思路

朴素想法与两个瓶颈。 枚举点集子集逐一验证断开与否是 $O(2^N(N+M))$ 的暴力， $N=100$ 不可行；而现成的网络流最小割模型切的是边，与"坏点"不匹配。把这两个障碍合起来看，需要解决的是：

点 vs 边：怎么让"坏一台电脑"变成"切断一条容量 1 的弧"？
字典序：一次最大流只给出"最小"的割，怎么拿到字典序最小的那一组？

瓶颈一：拆点。 把每台电脑 $v$ 拆成入点 $v_{in}$ 与出点 $v_{out}$ ，中间连一条容量 $1$ 的点弧——切断它恰好等价于坏掉这台电脑；原连接 $u$ - $v$ 改成 $u_{out} \to v_{in}$ 与 $v_{out} \to u_{in}$ 两条容量 $INF$ 的弧（坏的是电脑不是线）。 $c_1,c_2$ 不许坏，它们的点弧容量取 $INF$ ；源取 $c_1$ 入点、汇取 $c_2$ 入点。下面是样例网络拆点后的样子：

graph LR
    v1in["1 入"] =="容量 INF"==> v1out["1 出"]
    v1out =="容量 INF"==> v3in["3 入"]
    v3in -- "容量 1：坏电脑 3 就切这里" --> v3out["3 出"]
    v3out =="容量 INF"==> v2in["2 入"]
    v2in =="容量 INF"==> v2out["2 出"]
    style v3in fill:#f96,stroke:#333
    style v3out fill:#f96,stroke:#333

应观察到：整张网络里唯一容量有限的弧是 $3_{in} \to 3_{out}$ ，所以最小割大小为 $1$ ，切它就是坏掉电脑 3； $1$ 、 $2$ 的点弧是 $INF$ ，永远不会被选进割，天然满足"起止电脑不能坏"；连接弧全部 $INF$ 且双向（代码里每条弧还配一条容量 $0$ 的反向弧，供增广路回退流量）。拆点后按最大流最小割定理跑 Dinic，最大流 $=$ 最小点割大小 $k$ 。由于所有有限弧容量为 $1$ ，每次增广恰好推 $1$ ，流量不超过 $k \leqslant N$ 。

瓶颈二：字典序。 跑完一次最大流，取"残量网络中源点可达、出点不可达"的点，得到的只是一组最小割——但它离源最近，不保证字典序最小。反例是一条链：

text

11 —— 4 —— 3 —— 2        c1 = 1, c2 = 2

唯一增广路 $1 \to 4 \to 3 \to 2$ 上，点弧 $4_{in} \to 4_{out}$ 与 $3_{in} \to 3_{out}$ 都满流；残量网络里源只能走到 $4_{in}$ ，故可达割是 $\{4\}$ ，而 $\{3\}$ 同为最小割且字典序更小。真实数据也卡这一点：telecow1 的期望输出是 6 7 9，"一次最大流 + 可达割"却给出 9 17 19。

正解：升序逐点判定。 字典序最小即升序列表逐位最小，于是先求出最小点割大小 $k$ ，再按编号从小到大逐点决策，并维持不变量"存在一组大小为 $k$ 的最小割，包含全部已选点、避开全部已排除点"。轮到点 $v$ 时问：是否存在含 $v$ 的最小割？ 把已选点与 $v$ 当作已坏（点弧容量 $0$ ）、已排除点与 $c_1,c_2$ 设为不可坏（容量 $INF$ ），重跑最大流；记已选点集为 $C$ （代码里的 cut），还差的点数 $\text{rest} = k - \lvert C \rvert - 1$ 。该网络的最小割恒 $\geqslant \text{rest}$ （否则把该割并上已选点与 $v$ ，会得到小于 $k$ 的原图点割，矛盾），而"取等 $\Leftrightarrow$ 含 $v$ 的最小割存在"，所以判定条件就是 flow == rest：成立则收下 $v$ （这一位尽可能小），否则 $v$ 进入不可坏集合、任何最小割都不含它。链反例上的判定过程：

试探点 $v$	已选集 $C$ （`cut`）	$\text{rest} = k - \lvert C \rvert - 1$	$v$ 当已坏后 1 与 2 是否连通	重算 `flow`	判定
3	$\varnothing$	0	断开	0	$0 = 0$ ，收下 3
4	$\{3\}$	$-1$	断开	0	$0 \neq -1$ ，4 进不可坏集

表中 $k=1$ ：第一步含 3 的最小割存在，收下；第二步 $\text{rest}=-1$ 说明 $\{3\}$ 已凑满最小割，4 无须再坏。决策完所有点，不变量保证已选点集本身就是一组最小点割，且逐位取最小 ⇒ 全局字典序最小。样例 $1-3-2$ 同理： $k=1$ ，升序试探唯一点 3，把 3 当已坏后 1、2 断开，flow = 0 = rest，收下 3，输出 1 与 3。

代码

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
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#!/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-01 08:30
# update_at: 2026-10-01 09:46

import sys
from collections import deque

INF = 1 << 30  # 连接与起止电脑的容量：线路不会坏，c1/c2 不许坏


def build_net(n: int, adj: list[list[int]], broken: set[int], safe: set[int]) -> list[list[list[int]]]:
    """拆点建流网络：broken 里的电脑容量 0（当作已坏），safe 里容量 INF（不许坏），其余容量 1。"""
    net: list[list[list[int]]] = [[] for _ in range(2 * n + 2)]  # 点 v 的入点 2v、出点 2v+1

    def add_arc(u: int, v: int, cap: int) -> None:
        """加一对正反弧：反向弧初始容量 0，供增广路回退流量。"""
        net[u].append([v, cap, len(net[v])])
        net[v].append([u, 0, len(net[u]) - 1])

    for v in range(1, n + 1):
        # 点内部弧 v入->v出：容量 1 表示"拆掉这台电脑"的代价
        cap = 0 if v in broken else INF if v in safe else 1
        add_arc(2 * v, 2 * v + 1, cap)
    for u in range(1, n + 1):
        for v in adj[u]:
            if u < v:  # 每条无向连接拆成两个方向，容量 INF：坏的是电脑不是线
                add_arc(2 * u + 1, 2 * v, INF)
                add_arc(2 * v + 1, 2 * u, INF)
    return net


def max_flow(net: list[list[list[int]]], s: int, t: int) -> int:
    """Dinic 求 s 到 t 的最大流；按最大流最小割定理，它等于拆点网络的最小点割容量。"""
    flow = 0
    while True:
        level = [-1] * len(net)  # 分层图：只保留能层层推向 t 的弧
        level[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v, cap, _ in net[u]:
                if cap and level[v] < 0:
                    level[v] = level[u] + 1
                    queue.append(v)
        if level[t] < 0:
            return flow
        cur = [0] * len(net)

        def dfs(u: int) -> int:
            """在分层图上从 u 尽量往 t 推流，返回本条增广路推出的量。"""
            if u == t:
                return 1
            while cur[u] < len(net[u]):
                v, cap, rev = net[u][cur[u]]
                if cap and level[v] == level[u] + 1:
                    pushed = dfs(v)
                    if pushed:
                        net[u][cur[u]][1] -= pushed
                        net[v][rev][1] += pushed
                        return pushed
                cur[u] += 1
            return 0

        while (pushed := dfs(s)):  # 一层内榨干所有增广路再重新分层
            flow += pushed


def lex_min_cut(n: int, adj: list[list[int]], c1: int, c2: int) -> list[int]:
    """字典序最小的最小点割：先求最小割大小 k，再按编号从小到大逐点判定能否入选。"""
    safe: set[int] = {c1, c2}  # 起止电脑永远不许坏
    k = max_flow(build_net(n, adj, set(), safe), 2 * c1, 2 * c2)

    cut: list[int] = []
    for v in range(1, n + 1):
        if v in safe:
            continue  # 起止点与已排除点不再试探
        # 试探 v 入选：已选点当作已坏，已排除点设为不可坏；
        # 若剩余网络的最小割恰好 = 还差的点数 k-|cut|-1，则存在"含 v"的最小割
        rest = k - len(cut) - 1
        flow = max_flow(build_net(n, adj, set(cut) | {v}, safe), 2 * c1, 2 * c2)
        if flow == rest:  # 必有 flow >= rest，取等即说明含 v 的最小割存在
            cut.append(v)  # 收下 v，让答案这一位尽可能小
        else:
            safe.add(v)  # 含 v 达不到最小规模：任何最小割都不含 v
    return cut


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, c1, c2 = next(data), next(data), next(data), next(data)

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = next(data), next(data)
        adj[a].append(b)  # 连接双向
        adj[b].append(a)

    cut = lex_min_cut(n, adj, c1, c2)
    print(len(cut))
    print(' '.join(map(str, cut)))


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
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137/**
 * 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 12:40
 * update_at: 2026-10-06 12:40
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;                       // 电脑数上限
const int MAXV = 2 * MAXN + 5;              // 拆点后的点数上限
const int MAXM = 605;                       // 连接数上限
const int MAXE = 4 * MAXM + 2 * MAXN + 10;  // 每次建网的弧数上界（含反向弧）
const ll INF = 1e9;

ll n, m, c1, c2;
ll ea[MAXM], eb[MAXM];      // 每条无向连接的两端电脑
ll cut_id[MAXN], cut_cnt;   // 最小点割：已选中的坏电脑编号与个数

// 拆点网络：点 v 的入点是 2v，出点是 2v+1；链式前向星存弧
int head[MAXV], nxt[MAXE], to[MAXE];
ll cap[MAXE];
int e_cnt = 1;              // 弧计数从 1 开始、成对预增：弧对是 (2,3),(4,5)...，i^1 恰好是 i 的反向弧

ll level[MAXV], cur[MAXV];  // Dinic 的分层图与当前弧
ll s, t;                    // 源 = c1 的入点，汇 = c2 的入点
bool safe[MAXN];            // safe[v]=1：v 不许坏（起止点或已排除点）
bool broken[MAXN];          // broken[v]=1：v 当作已坏（点弧容量 0）

// 加一对正反弧：反向弧初始容量 0，供增广路回退流量
void add_arc(int u, int v, ll c) {
    ++e_cnt; // 正弧取偶数编号，i^1 才是反向弧
    to[e_cnt] = v; cap[e_cnt] = c; nxt[e_cnt] = head[u]; head[u] = e_cnt;
    e_cnt++;
    to[e_cnt] = u; cap[e_cnt] = 0; nxt[e_cnt] = head[v]; head[v] = e_cnt;
}

// 建网：坏点容量 0，不许坏点容量 INF，其余点容量 1；连接是双向 INF 线路
void build_net() {
    memset(head, 0, sizeof(head));
    e_cnt = 1; // 弧对从 (2,3) 开始，保证 i^1 配对成立
    for (ll v = 1; v <= n; v++) {
        ll c = 1;                       // 点内部弧 v入->v出：坏掉 v 的代价
        if (broken[v]) c = 0;
        else if (safe[v]) c = INF;      // c1、c2 的点弧是 INF，永远不会被切
        add_arc(2 * v, 2 * v + 1, c);
    }
    for (ll i = 1; i <= m; i++) {
        // 坏的是电脑不是线：每条连接拆成两个方向，容量 INF
        add_arc(2 * ea[i] + 1, 2 * eb[i], INF);
        add_arc(2 * eb[i] + 1, 2 * ea[i], INF);
    }
}

// BFS 分层：残量网络里从 s 出发能否层层推进到 t
bool bfs() {
    memset(level, -1, sizeof(level));
    queue<ll> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        ll u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            ll v = to[i];
            if (cap[i] > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != -1;
}

// 在分层图上从 u 尽量往 t 推流，返回这条路径推出的流量
ll dfs(ll u, ll pushed) {
    if (u == t) return pushed;
    for (ll &i = cur[u]; i; i = nxt[i]) {
        ll v = to[i];
        if (cap[i] > 0 && level[v] == level[u] + 1) {
            ll got = dfs(v, min(pushed, cap[i]));
            if (got > 0) {
                cap[i] -= got;
                cap[i ^ 1] += got;
                return got;
            }
        }
    }
    return 0;
}

// Dinic 最大流：按最大流最小割定理，它等于拆点网络的最小点割容量
ll dinic() {
    ll flow = 0;
    while (bfs()) {
        for (ll v = 0; v < 2 * n + 2; v++) cur[v] = head[v];
        while (ll got = dfs(s, INF)) flow += got;
    }
    return flow;
}

int main() {
    cin >> n >> m >> c1 >> c2;
    for (ll i = 1; i <= m; i++) cin >> ea[i] >> eb[i];

    s = 2 * c1;
    t = 2 * c2;
    safe[c1] = safe[c2] = true; // 起止电脑永远不许坏

    build_net();
    ll k = dinic(); // 先求最小点割的大小 k

    // 按编号从小到大逐点判定，保证答案字典序最小
    for (ll v = 1; v <= n; v++) {
        if (safe[v]) continue; // 起止点与已排除点不再试探
        ll rest = k - cut_cnt - 1; // 若选 v，最小割里还差的点数
        broken[v] = true;          // 把 v 当作已坏重跑最大流
        build_net();
        // 恒有 flow >= rest；取等 <=> 存在含 v 的最小割
        if (dinic() == rest) {
            cut_cnt++;
            cut_id[cut_cnt] = v; // 收下 v，让答案这一位尽可能小
        } else {
            broken[v] = false;
            safe[v] = true; // 任何最小割都不含 v，标记为不许坏
        }
    }

    cout << cut_cnt << "\n";
    for (ll i = 1; i <= cut_cnt; i++) {
        cout << cut_id[i] << (i < cut_cnt ? " " : "");
    }
    cout << "\n";
    return 0;
}

复杂度

时间复杂度：建网 $O(N+M)$ ；单次 Dinic 最坏 $O(V^2E)$ （ $V=2N$ ， $E=O(N+M)$ ，实际因点弧容量仅 $0/1$ 、流量 $\leqslant N$ 远小于最坏界）；共 $N+1$ 次最大流（求 $k$ 一次 + 每点判定一次），合计 $O(N \cdot V^2E)$ 量级。这是字典序要求本身的代价（逐位可行性判定），不是枚举点集的暴力。 $N \leqslant 100$ 下实测 11 组数据单点最长 $0.085$ s，对 $1000$ ms 很宽裕。
空间复杂度： $O(N+M)$ ，每次建网约 $2N + 4M$ 条弧，峰值约 $16$ MB，远低于 $128$ MB 限制。

总结

坏的是点不是边，先拆点：点弧容量 $1$ 表示坏一台电脑，连接弧容量 $INF$ ，起止点点弧 $INF$ 保证 $c_1,c_2$ 不会被坏；一次 Dinic 得到最小点割大小 $k$ 。但题目要字典序最小——“残量可达割"只离源最近并不最小字典序（链 $1-4-3-2$ 给 $\{4\}$ 而答案是 $\{3\}$ ），所以再按编号升序逐点重跑最大流，用 flow == rest 判定"含该点的最小割是否存在”，成立就收下。不变量保证最终已选集恰为一组最小点割且逐位最小。实测数据仓 11 组全部一致（PASS=11），最长单点 $0.085$ s、峰值 $15.6$ MB，相对 $1000$ ms / $128$ MB 的限制余量充足。

usaco-5.4.5 奶牛的电信

目录

形式化题目

正解

思路

代码

复杂度

总结