联络员

形式化题目

给定 $n$ 个点、 $m$ 条无向边，边分两类：必选边（无论费用必须全选）与可选边。要求选出若干边使得所有点连通（题目保证有解），最小化"全部必选边费用 + 所选可选边费用"之和。注意同一对 $u,v$ 间可能有多条必选边，费用全部要累加。

思路

一句话本质：必选边没有选择余地，先全部累加费用并用并查集把两端点连通；此后每个并查集集合就是一个"缩点"，剩下的任务是把若干个缩点连成一棵总体最省的树——对可选边按费用从小到大跑 Kruskal。

问题？ 朴素做法是什么，卡在哪？

枚举可选边的所有子集判连通再取最小费用， $m \leqslant 10^4$ 时子集数是天文数字，不可行。必须利用"必选边没有自由度"这一结构。

问题？ 必选边怎么处理？

必选边一定要选，费用直接累加进答案，与后面选什么无关。同时它们把图预先粘成了若干个连通块：用并查集把每条必选边两端合并。此后同一集合里的点已经"免费"连通，任何再连接它们的可选边都是多余的——连通性只需要在每个集合之间建立。

问题？ 剩下的问题变成什么？

把每个并查集集合看成一个超级点，可选边变成超级点之间带权的边，目标是选最少费用的边让所有超级点连通——这正是最小生成树。而且不需要真的缩点重建图：Kruskal 判"是否成环"用的就是并查集，直接在原并查集上继续做即可。

问题？ 为什么 Kruskal 是对的，会不会漏掉更优方案？

Kruskal 的贪心交换论证在此完全成立：任何连通所有缩点的方案都对应一棵生成树（砍掉多余边只会更省），而费用最小的生成树由 Kruskal 给出。必选边部分是常数，不参与比较。

问题？ 样例是怎么走完这个流程的？

用样例数据看两阶段：

阶段	边	动作	累计费用	连通块（用代表元表示）
必选	$1-2,2-3,3-4,4-1$ （各 $1$ ）	全选并合并	$4$	$\{1,2,3,4\},\{5\}$
可选排序	$(2,5,10),(2,5,5)$	排序后先看 $w=5$	$4$	同上
Kruskal	$2-5$ 费用 $5$	合并成功	$9$	$\{1,2,3,4,5\}$
Kruskal	$2-5$ 费用 $10$	已连通，跳过	$9$	全部连通

最终答案 $9$ ，与样例输出一致。注意两条 $2-5$ 重边：排序后便宜的先生效，贵的自然被"成环"判掉。

代码

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#!/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-07-05 21:50
# update_at: 2026-07-05 21:50

import sys

data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)

father = list(range(n + 1))  # 并查集父指针，0 号下标不占


def find(x: int) -> int:
    """找 x 的代表元，顺手路径压缩。"""
    root = x
    while father[root] != root:
        root = father[root]
    while father[x] != root:  # 第二遍把路径上的点全部挂到 root
        father[x], x = root, father[x]
    return root


# 第一遍：必选渠道全部累加费用并合并连通块
total = 0
optional: list[tuple[int, int, int]] = []  # (w, u, v) 可选渠道
for _ in range(m):
    p, u, v, w = next(data), next(data), next(data), next(data)
    if p == 1:
        total += w  # 同一对 u,v 的多条必选渠道全部要选，费用累加
        father[find(u)] = find(v)
    else:
        optional.append((w, u, v))

# 第二遍：对可选渠道按费用做 Kruskal，补齐连通块
for w, u, v in sorted(optional):
    ru, rv = find(u), find(v)
    if ru != rv:
        total += w
        father[ru] = rv

print(total)

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/**
 * 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 00:33
 * update_at: 2026-10-05 00:33
 */

// 解法：必选边先全部累加费用并并入并查集（相当于缩点），
// 剩下的任务就是把若干连通块用可选边连成最小生成树，
// 直接在同一套并查集上对可选边按费用跑 Kruskal 即可。

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

typedef long long ll;

const int MAXN = 2005;
const int MAXM = 10005;

int n, m;
int father[MAXN]; // 并查集父指针，下标 1..n

struct Edge {
    ll u;
    ll v;
    ll w;
};

Edge opt[MAXM]; // 只保存可选边 (u, v, w)

// 找 x 的代表元，顺手路径压缩
int find(int x) {
    int root = x;
    while (father[root] != root) root = father[root];
    while (father[x] != root) { // 第二遍把路径上的点全部挂到 root
        int t = father[x];
        father[x] = root;
        x = t;
    }
    return root;
}

// 比较两条可选边，费用小的排前面
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) father[i] = i; // 并查集初始化，每个点自成一块

    ll total = 0; // 答案：必选边费用 + 被选中的可选边费用
    int cnt = 0;  // 可选边的条数

    // 第一阶段：必选边没有自由度，费用直接累加，并把两端合并成一个连通块
    for (int i = 1; i <= m; i++) {
        int p, u, v;
        ll w;
        cin >> p >> u >> v >> w;
        if (p == 1) {
            total += w; // 同一对 u,v 的多条必选边全部要选，费用累加
            int ru = find(u), rv = find(v);
            if (ru != rv) father[ru] = rv;
        } else {
            cnt++;
            opt[cnt].u = u;
            opt[cnt].v = v;
            opt[cnt].w = w;
        }
    }

    // 第二阶段：每个并查集集合看成一个缩点，对可选边按费用做 Kruskal
    sort(opt + 1, opt + cnt + 1, cmp_edge);
    for (int i = 1; i <= cnt; i++) {
        int ru = find(opt[i].u), rv = find(opt[i].v);
        if (ru != rv) { // 不在一个连通块内，选这条边最划算
            total += opt[i].w;
            father[ru] = rv;
        }
    }

    cout << total << endl;
    return 0;
}

复杂度

时间：必选边一遍合并 $O(m\alpha(n))$ ，可选边排序 $O(m\log m)$ ，Kruskal 一遍 $O(m\alpha(n))$ ，总 $O(m\log m)$ 。
空间： $O(n+m)$ 存并查集与可选边。

总结

核心转化：无自由度的约束（必选边）先"结算"掉，把问题归约为标准的 MST。
缩点不必重建图：Kruskal 的并查集天然承担缩点职责，必选、可选两阶段共用一套 father。
可迁移思想："部分边强制选 + 其余求最优连通"类问题，套路都是强制边先并入并查集，再对自由边跑 Kruskal。

目录

形式化题目

思路

代码

复杂度

总结