最小割

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

把「恰好含一条树边的割」化归成 T-e 两侧的割,用树上边差分统计每条树边被多少条非树边跨过,答案即最小覆盖数加一。

OJ: roj

题目 ID: 1761

难度:提高+/省选-

标签:最小割生成树树上差分LCApython

创建: 2026-10-07 22:38

更新: 2026-10-07 22:38

形式化题目

给定无向无权简单图 G=(V,E)G=(V,E)(∣V∣=N|V| = N,∣E∣=M|E| = M,无重边无自环),并给出 GG 的一棵生成树 TT。 一个割是一组边,删去它之后图不连通;等价地,割由一个非平凡二分 (A,B)(A, B)(A∪B=VA \cup B = V, A,B≠∅A, B \neq \varnothing)给出,割边集就是两端分居 AA、BB 的边集。求

min⁡{ ∣δ(A,B)∣  :  A∪B=V, A,B≠∅, ∣δ(A,B)∩T∣=1 }, \min \bigl\{\, |\delta(A, B)| \;:\; A \cup B = V,\ A, B \neq \varnothing,\ |\delta(A,B) \cap T| = 1 \,\bigr\},

即在"恰好包含 TT 中一条边"的割里取边数最小者。多组数据:第一行组数 T0⩽5T_0 \leqslant 5; 每组第一行 N,MN, M(N⩽20000N \leqslant 20000,M⩽200000M \leqslant 200000),随后 N−1N-1 行是 TT 的树边, 再随后 M−N+1M-N+1 行是 GG 中不在 TT 中的边。每组输出一行答案。

正解

思路

第一步:割的形状被"恰好一条树边"锁死了。 TT 是生成树,任取非平凡二分 (A,B)(A,B), TT 中必然有边跨过它(否则 TT 会落在 AA 或 BB 内部,而不可能连通全部 NN 个点)。 所以 δ(A,B)∩T≠∅\delta(A,B) \cap T \neq \varnothing。现在要求它恰好只含一条边 ee:删掉 ee 后 TT 断成 两个连通块 V1,V2V_1, V_2,它们之间的树边只有 ee;既然 ee 是唯一跨过的树边, V1V_1、V2V_2 各自必须整体落在 AA 或 BB 里(块内若有边跨过割,那条边也是树边,矛盾)。 于是

A=V1,  B=V2或A=V2,  B=V1.A = V_1,\; B = V_2 \quad \text{或} \quad A = V_2,\; B = V_1 .

结论:一个合法的割与一条树边 ee 一一对应,它的边集是

δ(e)  =  {e}  ∪  { f∈E∖T  :  f 的两端分居 T−e 的两个连通块 }.\delta(e) \;=\; \{e\} \;\cup\; \{\, f \in E \setminus T \;:\; f \text{ 的两端分居 } T-e \text{ 的两个连通块} \,\}.

(TT 中的其他边都在某个块内部,跨不过去。)记 c(e)c(e) 为"跨过 T−eT-e 两个块的非树边条数", 则这个割的大小是 1+c(e)1 + c(e),答案就是

 1+min⁡e∈Tc(e) \boxed{\,1 + \min_{e \in T} c(e)\,}

第二步:c(e)c(e) 的几何含义。 GG 中每条非树边 f=(u,v)f=(u,v) 与 TT 上的 u ⁣− ⁣vu\!-\!v 路径合成一个 基本回路。ff 跨过 T−eT-e 的两个块   ⟺  \iff 路径 u ⁣− ⁣vu\!-\!v 经过树边 ee。所以

c(e)=#{ 基本回路经过 e 的非树边 },c(e) = \#\{\, \text{基本回路经过 } e \text{ 的非树边} \,\},

也就是"覆盖 ee 的非树边条数"。答案是 11 加上覆盖数最小的那条树边的覆盖数: 某条树边一条非树边都没覆盖(它是 GG 的桥),答案就是 11。

第三步:一次树上差分求出所有 c(e)c(e)。 以 11 为根把 TT 定根,把树边 (par[x],x)(\mathrm{par}[x], x) 的值记在节点 xx 上。对每条非树边 (u,v)(u,v),要给 u ⁣− ⁣vu\!-\!v 路径上的所有树边 +1+1:

diff[u]+=1,diff[v]+=1,diff[lca(u,v)]−=2.\mathrm{diff}[u] \mathrel{+}= 1, \qquad \mathrm{diff}[v] \mathrel{+}= 1, \qquad \mathrm{diff}[\mathrm{lca}(u,v)] \mathrel{-}= 2 .

然后把 diff\mathrm{diff} 按逆 BFS 序自底向上做子树和:处理完所有孩子之后, 节点 xx 上的值就是树边 (par[x],x)(\mathrm{par}[x], x) 的覆盖数 cc。为什么正确?子树和 diff[x]\mathrm{diff}[x] 等于"子树内非树边端点个数"减去 22 倍的"两端都在子树内的非树边条数", 正是恰好一个端点在子树内的非树边条数,也就是跨过这条树边的非树边条数。

用样例验一遍(N=4N=4,TT 是链 1−2−3−41-2-3-4,非树边 1 ⁣− ⁣31\!-\!3、1 ⁣− ⁣41\!-\!4):

树边 ee T−eT-e 的两块 跨过的非树边 c(e)c(e) 割的大小
1−21-2 {1}∣{2,3,4}\{1\}\mid\{2,3,4\} 1 ⁣− ⁣31\!-\!3、1 ⁣− ⁣41\!-\!4 2 3
2−32-3 {1,2}∣{3,4}\{1,2\}\mid\{3,4\} 1 ⁣− ⁣31\!-\!3、1 ⁣− ⁣41\!-\!4 2 3
3−43-4 {1,2,3}∣{4}\{1,2,3\}\mid\{4\} 1 ⁣− ⁣41\!-\!4 1 2

最小是 3−43-4 对应的割 {3 ⁣− ⁣4,  1 ⁣− ⁣4}\{3\!-\!4,\;1\!-\!4\},大小 22,与样例输出一致。

LCA 怎么求。 N⩽20000N \leqslant 20000、M⩽200000M \leqslant 200000、T0⩽5T_0 \leqslant 5,合计 10610^6 条非树边, 需要 10610^6 次 LCA。O(log⁡N)O(\log N) 的倍增法总共约 3×1073 \times 10^7 次操作,C++ 里毫无压力 (实测单点最大 2020 ms、55 组顶格的 problem10 约 7070 ms),Python 里则偏慢, 所以 main.py 换成欧拉序 + 稀疏表的 O(1)O(1) LCA:欧拉序长 2N−12N-1,u,vu,v 的 LCA 就是 first[u]…first[v]\mathrm{first}[u] \dots \mathrm{first}[v] 区间里深度最小的节点,稀疏表把区间取最小压成常数次操作。两种实现复杂度同阶 (O(Nlog⁡N+M)O(N \log N + M)),Python 只是把每次询问的常数再压小一截。

实现要点。

  • 建树用迭代 BFS / 迭代 DFS,链状树(N=20000N=20000 深链是数据里的最坏形状)不会爆栈。
  • 多组数据、每组上界 N=20000N=20000、M=200000M=200000,输入量到 2×1062 \times 10^6 个数, C++ 用 fread 快读。
  • 数组每次进新一组都要重置(head 置 -1、diffCnt 清 00)。
  • 退化输入 N=1N=1:TT 没有边,不存在"恰好含一条 TT 边"的割,两种实现都输出 00 并在代码里注明。题面约束 M⩾N−1M \geqslant N-1 且无自环,所以这个分支在真实数据里不可达。

代码

Python 版(欧拉序 + 稀疏表 LCA,树上差分):

python
#!/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-07 22:38
# update_at: 2026-10-07 22:38

import sys

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[list[int]]    # 生成树的邻接表:adj[x] 是 x 的所有邻居
type Sparse = list[list[int]] # 欧拉序上的 RMQ 稀疏表,第 k 层窗口长 2^k,存深度最小的节点
type Lca = tuple[list[int], Sparse, list[int], list[int]]  # (欧拉序, 稀疏表, 首次出现位置, 深度)


def rooted_tree(adj: Adj, n: int) -> tuple[list[int], list[int], list[int]]:
    """以 1 为根 BFS,返回 (父亲, 深度, BFS 序);BFS 序倒着扫就是自底向上的累加顺序。"""
    par = [0] * (n + 1)
    dep = [0] * (n + 1)
    order = [1]
    for u in order:                     # 边遍历边追加,等价于一个队列
        for v in adj[u]:
            if v != par[u]:             # 树里除父亲外都是孩子,不需要额外判重
                par[v] = u
                dep[v] = dep[u] + 1
                order.append(v)
    return par, dep, order


def euler_tour(adj: Adj, par: list[int], n: int) -> tuple[list[int], list[int]]:
    """迭代 DFS 求欧拉序(长 2n-1)与每个节点首次出现的位置。

    进入节点与回退到父节点各记一笔,于是 u、v 的 LCA 恰好是欧拉序上
    first[u]..first[v] 这段区间里深度最小的那个节点。
    """
    euler = [1]
    first = [0] * (n + 1)
    ptr = [0] * (n + 1)                 # ptr[x] 指向 adj[x] 里下一个待访问的邻居
    stack = [1]
    while stack:
        u = stack[-1]
        if ptr[u] < len(adj[u]):
            v = adj[u][ptr[u]]
            ptr[u] += 1
            if v != par[u]:
                first[v] = len(euler)   # 树的 DFS 里 v 只可能由父亲首次走到
                euler.append(v)
                stack.append(v)
        else:
            stack.pop()
            if stack:
                euler.append(stack[-1]) # 回退到父节点,再记一笔
    return euler, first


def rmq_table(euler: list[int], dep: list[int]) -> Sparse:
    """对欧拉序建稀疏表:第 k 层存窗口长 2^k 内深度最小的节点,供 O(1) 区间取最小。"""
    table: Sparse = [euler]             # 第 0 层窗口长 1,就是欧拉序本身
    while 1 << len(table) <= len(euler):
        prev = table[-1]
        half = 1 << (len(table) - 1)
        table.append([a if dep[a] < dep[b] else b for a, b in zip(prev, prev[half:])])
    return table


def cover_counts(eu: list[int], ev: list[int], lca: Lca) -> list[int]:
    """树上边差分:每条非树边 (u,v) 给 u-v 树上路径上的每条树边加一。

    树边 (par[x], x) 的值记在节点 x 上,于是每条非树边做
    diff[u]++, diff[v]++, diff[LCA] -= 2;之后按 BFS 序倒着做子树和,
    节点 x 的值就是覆盖树边 (par[x], x) 的非树边条数。
    """
    euler, table, first, dep = lca
    diff = [0] * len(dep)
    for u, v in zip(eu, ev):
        l, r = first[u], first[v]
        if l > r:
            l, r = r, l
        k = (r - l + 1).bit_length() - 1   # 覆盖 [l, r] 的层号:2^k <= r-l+1
        row = table[k]
        a = row[l]
        b = row[r - (1 << k) + 1]
        w = a if dep[a] < dep[b] else b    # 区间内深度最小的节点就是 LCA
        diff[u] += 1
        diff[v] += 1
        diff[w] -= 2
    return diff


def min_cut_answer(diff: list[int], order: list[int], par: list[int]) -> int:
    """恰好含一条树边的割的最小边数:树边 (par[x], x) 的覆盖数 + 1,取最小。

    逆 BFS 序做子树和(孩子的值先并给父亲)之后,diff[x] 就是跨过树边
    (par[x], x) 的非树边条数,于是该割的边数 = 覆盖数 + 1。
    """
    for x in reversed(order[1:]):
        diff[par[x]] += diff[x]
    best = min((diff[x] for x in order[1:]), default=-1)  # 无树边时(约束外)输出 0
    return best + 1


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

    for _ in range(T):
        n, m = next(data), next(data)

        adj: Adj = [[] for _ in range(n + 1)]
        for _ in range(n - 1):              # 先读生成树 T 的 N-1 条边
            u, v = next(data), next(data)
            adj[u].append(v)
            adj[v].append(u)

        extra = m - n + 1                   # 题面:其余 M-N+1 条边不在 T 中
        eu = [0] * extra
        ev = [0] * extra
        for i in range(extra):
            eu[i], ev[i] = next(data), next(data)

        par, dep, order = rooted_tree(adj, n)
        euler, first = euler_tour(adj, par, n)
        diff = cover_counts(eu, ev, (euler, rmq_table(euler, dep), first, dep))
        out.append(str(min_cut_answer(diff, order, par)))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版(同一算法,LCA 用倍增):

cpp
/**
 * 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-07 22:38
 * update_at: 2026-10-07 22:38
 */
// main.cpp:最小割(一本通 1761 / ROJ 1761)。
// 关键结论:割里恰好含 T 的一条边 e ⇔ 割的两侧就是 T-e 的两个连通块
// (T 是生成树,任一非平凡割至少跨过一条树边,跨过恰好一条就只能是 e),
// 于是该割大小 = 1 + cover[e],cover[e] 是基本回路经过 e 的非树边条数。
// 答案 = 1 + min cover[e],cover 用树上边差分(非树边给 u-v 路径 +1)统计。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 20005;      // N <= 20000,留一点安全余量
const int MAXARC = 2 * MAXN; // 生成树邻接表:N-1 条树边 → 2(N-1) 条弧
const int LOG = 16;          // 2^15 = 32768 > 20000,16 层足够且留一层余量

int head[MAXN], nxt[MAXARC], to[MAXARC], arcCnt; // 生成树的链式前向星
int par[MAXN], dep[MAXN];                        // 以 1 为根:父亲与深度
int up[LOG][MAXN];                               // 倍增祖先,up[0][x] = par[x]
ll diffCnt[MAXN];                                // 树上边差分的累加数组
int order[MAXN];                                 // BFS 序,倒着扫就是自底向上

void addArc(int u, int v) {
    to[arcCnt] = v;
    nxt[arcCnt] = head[u];
    head[u] = arcCnt++;
}

// 快读:最大输入约 10^6 条边(2×10^6 个数),fread 缓冲比 scanf 稳
const int BUFSZ = 1 << 16;
char buf[BUFSZ];
int bufLen = 0, bufPos = 0;

int readChar() {
    if (bufPos == bufLen) {
        bufLen = fread(buf, 1, BUFSZ, stdin);
        bufPos = 0;
        if (bufLen <= 0) return -1; // EOF
    }
    return buf[bufPos++];
}

// 本题所有输入都是非负整数,读到 EOF 就返回已累积的值
int readInt() {
    int c = readChar();
    while (c >= 0 && (c < '0' || c > '9')) c = readChar(); // 跳过空白与换行
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readChar();
    }
    return x;
}

// u、v 的最近公共祖先(倍增法,本题 N 小,倍增足够)
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (d >> k & 1) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    return up[0][u];
}

int main() {
    ll T = readInt();
    if (T < 0) T = 0;
    while (T-- > 0) {
        ll n = readInt(), m = readInt();

        arcCnt = 0;
        for (int i = 1; i <= n; i++) {
            head[i] = -1;
            diffCnt[i] = 0;
        }

        for (int i = 0; i < n - 1; i++) { // 生成树 T 的 N-1 条边
            int u = readInt(), v = readInt();
            addArc(u, v);
            addArc(v, u);
        }

        if (n <= 1) { // 退化输入:T 没有树边,不存在"恰好含一条 T 边"的割(约束外)
            for (ll i = 0; i < m; i++) {
                readInt();
                readInt();
            }
            printf("0\n");
            continue;
        }

        // 迭代 BFS 建树(链状树也不会爆栈),同时把倍增祖先预处理出来
        int qh = 0, qt = 0;
        order[qt++] = 1;
        par[1] = 0;
        dep[1] = 0;
        for (int k = 0; k < LOG; k++) up[k][1] = 0;
        while (qh < qt) {
            int u = order[qh++];
            for (int e = head[u]; e != -1; e = nxt[e]) {
                int v = to[e];
                if (v == par[u]) continue;
                par[v] = u;
                dep[v] = dep[u] + 1;
                up[0][v] = u;
                for (int k = 1; k < LOG; k++) up[k][v] = up[k - 1][up[k - 1][v]];
                order[qt++] = v;
            }
        }

        // 非树边:树上边差分,u-v 路径上所有树边 +1
        ll extra = m - n + 1; // 题面:M-N+1 条不在 T 中的边
        for (ll i = 0; i < extra; i++) {
            int u = readInt(), v = readInt();
            int w = lca(u, v);
            diffCnt[u]++;
            diffCnt[v]++;
            diffCnt[w] -= 2;
        }

        // 逆 BFS 序做子树和:节点 x 累加后的值就是树边 (par[x], x) 的覆盖数
        ll best = -1;
        for (int idx = n - 1; idx >= 1; idx--) {
            int x = order[idx];
            ll c = diffCnt[x];
            if (best < 0 || c < best) best = c;
            diffCnt[par[x]] += c;
        }

        printf("%lld\n", best + 1);
    }
    return 0;
}

复杂度

  • 时间:每组 O(Nlog⁡N+M)O(N \log N + M)。C++ 版是 O((N+M)log⁡N)O((N+M)\log N)(每条非树边一次 O(log⁡N)O(\log N) 的 LCA); Python 版建稀疏表 O(Nlog⁡N)O(N \log N)、每条非树边 O(1)O(1),同阶。按题面顶格数据 T0=5T_0=5、N=20000N=20000、M=200000M=200000(合计 10610^6 条边),C++ 版实测 problem10 约 7070 ms, 远低于 40004000 ms 限时;Python 版同一测试点约 0.40.4 s(本题 Python 无需担心 TLE)。
  • 空间:C++ 版 O(Nlog⁡N+N)O(N \log N + N)(倍增表 16×2000516 \times 20005 个 int,约 1.31.3 MB); Python 版稀疏表约 Nlog⁡NN \log N 个整数引用。两者都在 256256 MB 之内。

总结

  • 先给"合法割"定性,再谈算法:本题最容易卡住的地方不是数据结构,而是"恰好含一条树边" 这个条件的含义。想清楚"跨过割的树边唯一 ⇒\Rightarrow 割的两侧就是 T−eT-e 的两个连通块", 问题立刻退化成"给每条树边数一数有多少非树边跨过它"。
  • 把"跨过割"翻译成"基本回路经过":非树边 ff 跨过 T−eT-e 当且仅当 ff 的基本回路含 ee, 于是一条边的覆盖数就有了两种等价视角,差分统计的合法性也来自这里。
  • 树上差分是"多条路径 +1+1"的标准解法:端点 +1+1、LCA −2-2、子树和还原, 这三步合起来是 O(N+M)O(N+M) 的(不含 LCA 的 log⁡\log),比"枚举每条树边再扫一遍非树边"的 O(NM)O(NM) 快了一个量级。
  • 答案下界是 11:若某条树边是 GG 的桥,c(e)=0c(e)=0,最小割就是这条桥本身。
  • 数据与题源说明:本题素材目录里带有数据生成脚本 data.py,说明 data/ 的 1010 个测试点 是自造的(按题面上限分层生成:边界 N=2N=2 → 小规模 → 顶格 N=20000,M=200000N=20000,M=200000 → 多组顶格 T0=5T_0=5,树形状覆盖链 / 星 / 随机并含随机重标号);题面本身是网络重建版本, 与官方原题的措辞、数据强度可能不完全一致。目录里的 std.cpp 是自研标程(其头注释也说明 未检索到公开题解),它与本题解互相印证:data/*.out 就是 std.cpp 的产物, 本题解对 1010 个测试点逐点比对 10/1010/10 一致;另外我还写了一份枚举全部二分的 暴力(不依赖本题结论)对 12001200 组 N⩽8N \leqslant 8 的随机小数据验证,同样全部一致。