「一本通 3.7 练习 5」相框

形式化题目

给定一张无向图： $n$ 个焊点（标号 $1 \sim n$ ）与 $m$ 根导线，每根导线连接两个焊点；若某一端为 $0$ ，表示该端是自由端，没有接到任何焊点上。

允许两种操作，每次操作计 $1$ 步：

烧熔一个焊点：把接在该焊点上的所有导线端重新分成若干组，同一组内的端仍然相连，不同组之间分离；
焊接两个自由端：把两根导线的自由端接在一起。

要求用上全部导线，把它们首尾相接成闭环（相框）。图可能不连通，每个连通块各自收成一个环即可。求最少操作步数。

限制条件：如果某个焊点只接了一根导线（度数为 $1$ ），那么在该导线的这一端被连到别的导线之前，不允许烧熔这个焊点；没有接任何导线的焊点可以直接忽略。数据范围 $0 \leqslant n \leqslant 1000$ ， $2 \leqslant m \leqslant 50000$ 。

正解

思路

一个连通块能被一笔画完并回到起点，等价于块内每个顶点的度数都是偶数（欧拉回路）。所以"改造成相框"这件事，只和每个块的度数奇偶、以及度数太高的点有关。下面分三笔账算。

第一笔：奇端配对，需要 $o/2$ 次焊接。

对每个连通块，设

o = \text{(块内奇度焊点数)} + \text{(块内自由端数)}.

一次焊接只能同时消掉两个奇端，所以至少需要 $o/2$ 步；而自由端本来就是裸露的线头，两两焊上正好消掉，所以 $o/2$ 步可以做到。由握手定理， $o$ 一定是偶数。

第二笔：度数大于 $2$ 的焊点必须烧熔。

设块内度数 $> 2$ 的焊点个数为 $high$ 。这样一个焊点上挂着 $3,4,5,\dots$ 个线头，如果不烧熔，它的度数就保持不变，在"一笔画"里无法把多余的分支拆开，环就走不通。烧熔一次就可以把它的线头任意分组，因此每个这样的焊点贡献 $1$ 步，共 $high$ 步。反过来，度数 $\leqslant 2$ 的焊点本身不挡路，不需要处理。

第三笔：已经闭合的块要"烧开再焊回"。

如果某个块满足 $o = 0$ ，说明它内部度数已经全偶、也没有自由端，它自己就已经是一个闭环了。但相框要求所有导线串在同一个环上，这个块必须被打开一次再合上：至少 $1$ 次烧熔加 $1$ 次焊接，也就是 $2$ 步。如果块里本来就有 $high$ 个高次点，那么烧熔这些点的同时就已经把它打开了，只需额外多 $1$ 步，于是代价是 $high + 1$ 。

综合三笔账，每个连通块的代价为

\text{cost} = \begin{cases} high + \dfrac{o}{2}, & o > 0,\\[2mm] \max\left(2,\ high + 1\right), & o = 0. \end{cases}

答案就是所有块的 $\text{cost}$ 之和。

下面用输入样例说明这些量怎么算。样例是一个连通块：

text

1
2
3
4
5
6
7
8
96 8
1 2      各点度数： deg[1]=4  deg[2]=1  deg[3]=2
1 3                 deg[4]=4  deg[5]=3  deg[6]=2
3 4
1 4
4 6
5 6
4 5
1 5

量	取值	说明
奇度焊点	$2$ 个（点 $2$ 、点 $5$ ）	度数为 $1$ 和 $3$
自由端	$0$ 个	没有端点为 $0$ 的导线
$o$	$2 + 0 = 2$	需要 $o/2 = 1$ 次焊接
$high$	$3$ 个（点 $1$ 、点 $4$ 、点 $5$ ）	度数为 $4,4,3$ ，都 $>2$
cost	$3 + 2/2 = 4$	与样例输出一致

图中这块由 $1$ 和 $4$ 两个"十字路口"（度数 $4$ ）把导线织在一起，必须把它们分别烧熔拆成偶度，再补一次焊接把剩下的两个奇端接上：

graph LR
    A((1)) --- B((2))
    A --- C((3))
    A --- E((4))
    A --- F((5))
    E --- D((6))
    E --- F
    F --- D
    classDef odd fill:#ffe0e0,stroke:#c00
    classDef hi fill:#e0f0ff,stroke:#06c
    class B,F odd
    class A,E hi

红色是奇度点（点 $2$ 、点 $5$ ， $o$ 的来源），蓝色是度数 $>2$ 的点（点 $1$ 、点 $4$ ， $high$ 的来源）。烧熔点 $1$ 、点 $4$ 、点 $5$ 花 $3$ 步，再把拆出来的两个奇端焊到一起花 $1$ 步，总共 $4$ 步。

注意几个边界情形：

单根两端都是自由端的导线 $0\text{-}0$ ： $o = 2$ ，代价 $1$ （把两个线头焊成一个自环）；
自环导线 $v\text{-}v$ ： $o = 0$ 、 $high = 0$ ，代价 $\max(2, 0+1) = 2$ ；
两点之间的平行边（ $1\text{-}2$ 与 $2\text{-}1$ ）：同样 $o = 0$ ，代价 $2$ ；
一条路径：只有两个端点度为 $1$ ， $o = 2$ ，代价 $1$ ；
$n = 0$ ：没有焊点，每根导线都是 $0\text{-}0$ ，每根贡献 $1$ 。

实现上只需要并查集把共享焊点的导线并成连通块（两端都为 $0$ 的导线各自单独成块），再按块累计三个计数器 $odd, free, high$ 即可。

代码

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#!/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-09-30 17:00
# update_at: 2026-09-30 17:00

import sys
from collections import defaultdict


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    wires = [(next(data), next(data)) for _ in range(m)]  # 每根导线两端，端点为 0 表示自由端

    # 并查集：把同一焊点上的导线并成一个连通块。端点 0 不是焊点，不参与合并。
    parent = list(range(n + 1))

    def find(x: int) -> int:
        """返回 x 所在连通块的代表元，路径压缩。"""
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in wires:
        if a and b:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb

    # 每个连通块累计三件事：奇数度焊点数、自由端数、度数 > 2 的焊点数。
    # 度数从导线端点统计，节点 0 单独记成"自由端"。
    deg: dict[int, int] = defaultdict(int)
    blocks: dict[object, list[int]] = defaultdict(lambda: [0, 0, 0])  # [odd, free, high]
    for i, (a, b) in enumerate(wires):
        if a and b:
            key = find(a)
        elif a:
            key = find(a)
        elif b:
            key = find(b)
        else:
            key = ("lone", i)  # 两端都自由的导线自己就是一个连通块
        blocks[key][1] += (a == 0) + (b == 0)
    for a, b in wires:
        for x in (a, b):
            if x:
                deg[x] += 1
    for v, d in deg.items():
        blocks[find(v)][0] += d % 2
        blocks[find(v)][2] += d > 2

    # 每个连通块独立算代价再求和：
    # 奇端数 o 必须两两焊接，贡献 o/2 次焊接；度数 > 2 的焊点要烧熔拆开，贡献 high 次。
    # o == 0 说明它本身已经闭合成环，要先烧开再焊回去，代价至少 2。
    total = 0
    for odd, free, high in blocks.values():
        o = odd + free
        total += high + o // 2 if o else max(2, high + 1)

    print(total)


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/**
 * 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-05 06:54
 * update_at: 2026-10-05 06:54
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;
const int MAXM = 50005;

ll n;               // 焊点数
ll m;               // 导线数
int fa[MAXN];       // 并查集：fa[i] 表示焊点 i 的父亲
int deg[MAXN];      // deg[i] 表示焊点 i 上的导线端数（度数）
ll cntOdd[MAXN];    // 每个连通块内奇度焊点个数
ll cntFree[MAXN];   // 每个连通块内自由端个数
ll cntHigh[MAXN];   // 每个连通块内度数 > 2 的焊点个数
ll done[MAXN];      // done[i] 表示焊点 i 所在块是否已统计过答案
ll u[MAXM], v[MAXM]; // 每根导线两端的焊点标号，0 表示自由端

// 并查集查找（路径压缩）。
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
    }
}

void solve() {
    // 初始化并查集
    for (int i = 0; i <= n; i++) fa[i] = i;

    // 有公共焊点的导线合并进同一个连通块；端点 0 是自由端，不参与合并
    for (int i = 1; i <= m; i++) {
        if (u[i] && v[i]) {
            int ru = find(u[i]);
            int rv = find(v[i]);
            if (ru != rv) fa[ru] = rv;
        }
    }

    // 按块累计三个计数器
    for (int i = 1; i <= m; i++) {
        // 自由端计入所在块的 cntFree；两端都自由的导线自己单独成块（见下面答案统计）
        if (!u[i]) cntFree[find(v[i])]++;
        if (!v[i]) cntFree[find(u[i])]++;
    }
    for (int i = 1; i <= n; i++) {
        deg[i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        if (u[i]) deg[u[i]]++;
        if (v[i]) deg[v[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 0) {
            if (deg[i] % 2 == 1) cntOdd[find(i)]++;
            if (deg[i] > 2) cntHigh[find(i)]++;
        }
    }

    // 每个连通块独立算代价再求和：
    // 奇端数 o 必须两两焊接，贡献 o/2 次焊接；度数 > 2 的焊点要烧熔拆开，贡献 high 次。
    // o == 0 说明这块本身已经闭合成环，要先烧开再焊回去，代价至少 2；
    // 若块内有 high 个高次点，烧熔时顺带打开，只需再多 1 次焊接，即 max(2, high+1)。
    // 两端都自由的导线（0-0）不属于任何焊点的块，o = 2，单独贡献 1 次焊接。
    ll ans = 0;
    ll loneWires = 0; // 两端都是自由端的导线数
    for (int i = 1; i <= m; i++) {
        if (!u[i] && !v[i]) loneWires++;
    }

    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) continue; // 没接导线的焊点不用考虑
        int r = find(i);
        if (done[r]) continue;
        done[r] = 1;
        ll o = cntOdd[r] + cntFree[r];
        if (o > 0) {
            ans += cntHigh[r] + o / 2;
        } else {
            ans += max(2LL, cntHigh[r] + 1);
        }
    }
    ans += loneWires; // 每根 0-0 导线自成一块，o = 2，代价 1

    cout << ans << endl;
}

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

    read_input();
    solve();

    return 0;
}

复杂度

并查集带路径压缩，时间 $O(m\,\alpha(n))$ ，空间 $O(n + m)$ 。对 $m \leqslant 50000$ 的数据，Python 实现实测单组最慢 $0.02$ s、峰值内存约 $15$ MB。

总结

把导线当边、焊点当点，按连通块统计奇端数 $o$ 与度数大于 $2$ 的焊点数 $high$ ： $o > 0$ 的块代价是 $high + o/2$ ， $o = 0$ 的块已被封闭，代价是 $\max(2, high+1)$ ；全部相加即为答案。

「一本通 3.7 练习 5」相框

目录

形式化题目

正解

思路

代码

复杂度

总结