[CSP-S 2025] 道路修复

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

枚举被城市化的乡镇集合，并用“原图边只需 MST”的替换性质把每次 Kruskal 的原图边压缩到 n-1 条。

OJ: luogu

题目 ID: P14362

难度:提高+/省选-

标签:图论最小生成树枚举并查集

创建: 2026-06-22 19:46

更新: 2026-10-07 12:15

前置题目

luogu P2504[HAOI2006] 聪明的猴子B 的每个子集解法复用 A 教的最小生成树求最小连接费用这一步，再叠加枚举乡镇子集与原图 MST 替换性质的交换论证 luogu P4047[JSOI2010] 部落划分B 沿用 A 的 Kruskal 并查集逐边合并建生成树骨架，枚举乡镇子集把修复边与建路边合并跑 Kruskal 再优化掉重复排序

形式化题目

$n$ 座原有城市之间有 $m$ 条双向道路，第 $i$ 条连接 $u_i,v_i$ ，修复费用 $w_i$ 。原有城市两两连通。

另有 $k$ 个乡镇。选中乡镇 $j$ 要先付 $c_j$ ，之后可以在它与原有城市 $i$ 之间建路，费用 $a_{j,i}$ 。乡镇只能与原有城市相连，且可以选择任意子集（含空集）。

求让原有 $n$ 座城市两两连通的最小总费用。

暴力解法

思路

$k\leqslant10$ ，直接枚举被城市化的乡镇集合 $S$ 。对每个 $S$ ，把「原有 $m$ 条修复边」与「 $S$ 中乡镇到城市的建路边」倒在一起跑一次 Kruskal，再加上 $S$ 的改造费用，取所有 $S$ 的最小值。

生成树需要结点数减一条边，所以扫描到 $n+|S|-1$ 条边就停。

代码

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
138
139/**
 * 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 23:04
 * update_at: 2026-10-01 23:04
 */
// brute.cpp：小数据暴力解，每个乡镇子集都用全部原图边重新跑一次 Kruskal。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 20;   // 暴力只服务小数据，n、m 取到 20 左右
const int MAXK = 5;    // k 不能大，要枚举 2^k 个子集
const ll INF = 1LL << 62;

// 一条无向边：端点 u、v，费用 w。
struct Edge {
    int u;
    int v;
    ll w;
};

// 按边权升序，Kruskal 需要。
bool cmp_edge(const Edge &x, const Edge &y) {
    return x.w < y.w;
}

int n, m, k;
ll town_cost[MAXK];   // town_cost[j]：把第 j 个乡镇城市化的固定费用
ll town_a[MAXK][MAXN]; // town_a[j][i]：乡镇 j 到城市 i 建路的费用

vector<Edge> original_edges; // 原有城市之间的全部 m 条边

int fa[MAXN + MAXK];   // 并查集父亲
int sz[MAXN + MAXK];   // 并查集连通块大小

void init_dsu(int total) {
    for (int i = 1; i <= total; i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}

int find_set(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

bool unite_set(int x, int y) {
    int fx = find_set(x);
    int fy = find_set(y);
    if (fx == fy) {
        return false;
    }
    if (sz[fx] < sz[fy]) {
        swap(fx, fy);
    }
    fa[fy] = fx;
    sz[fx] += sz[fy];
    return true;
}

// 对固定的一组乡镇，直接把所有可用边倒出来跑 Kruskal。
ll solve_mask(int mask) {
    vector<Edge> edges = original_edges;
    ll cost = 0;
    int selected_towns = 0;

    for (int j = 0; j < k; j++) {
        if ((mask & (1 << j)) == 0) {
            continue;
        }
        selected_towns++;
        cost += town_cost[j];

        for (int i = 1; i <= n; i++) {
            Edge e;
            e.u = i;
            e.v = n + j + 1;
            e.w = town_a[j][i];
            edges.push_back(e);
        }
    }

    sort(edges.begin(), edges.end(), cmp_edge);
    init_dsu(n + k);

    // 生成树需要结点数减一条边。
    int need_edges = n + selected_towns - 1;
    int picked = 0;
    int cnt = edges.size();
    for (int i = 0; i < cnt && picked < need_edges; i++) {
        if (unite_set(edges[i].u, edges[i].v)) {
            cost += edges[i].w;
            picked++;
        }
    }

    if (picked < need_edges) {
        return INF;
    }
    return cost;
}

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

    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++) {
        Edge e;
        cin >> e.u >> e.v >> e.w;
        original_edges.push_back(e);
    }
    for (int j = 0; j < k; j++) {
        cin >> town_cost[j];
        for (int i = 1; i <= n; i++) {
            cin >> town_a[j][i];
        }
    }

    // 枚举所有乡镇子集，取最小费用。
    ll ans = INF;
    for (int mask = 0; mask < (1 << k); mask++) {
        ll current = solve_mask(mask);
        if (current < ans) {
            ans = current;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

枚举 $2^k$ 个子集，每个子集把全部边重新排序一次： $O(2^k\cdot(m+nk)\log(m+nk))$ 。空间 $O(m+nk)$ 。

瓶颈

$m$ 最大 $10^6$ ，每个子集都重新排序并扫描全部原图边， $2^k$ 一乘就爆了。真正反复处理的只有那 $m$ 条原图边——乡镇边本来就只有 $nk=10^5$ 条。所以要解决的是：原图边能不能只处理一次。

正解

思路

固定乡镇集合后，问题就是扩展图的最小生成树

若某个已城市化的乡镇没有连任何道路，它对连通性没有贡献，取消它的城市化不会更贵也不会破坏连通性。所以存在最优方案，其中每个被选中的乡镇都至少连了一条路。

于是固定集合 $S$ 后，把「原有城市 + $S$ 中的乡镇」看成一张扩展图，边为原有 $m$ 条修复边加 $S$ 中乡镇的建路边。边权都非负，可以删掉连通方案中的环而不增加费用，所以最小连接费用就是这张扩展图的最小生成树费用，再加 $S$ 的改造费用。

关键观察：原图边只需保留一棵 MST

记只含原有城市和原有道路的图为 $G$ ，它的一棵最小生成树为 $T$ 。固定 $S$ 后，扩展图的一棵最优生成树为 $F$ 。

要证的不是“每棵 $F$ 都只用 $T$ 的原图边”，而是至少存在一棵同样优的 $F$ ，它用到的原图边全部属于 $T$ 。这样删掉其他原图边就不改变最优答案。

交换论证。设 $F$ 用了一条不属于 $T$ 的原图边 $e=(u,v,w)$ ：

从 $F$ 删掉 $e$ ，分成连通块 $A,B$ ，其中 $u\in A$ 、 $v\in B$ ；
在树 $T$ 中 $u$ 到 $v$ 有唯一路径，它从 $A$ 走到 $B$ ，故路径上必有一条边 $f$ 跨越 $A,B$ ；
这条路径上每条边权都不超过 $w$ ：否则用 $e$ 替换那条更重的边，会得到比 $T$ 更小的原图生成树，与 $T$ 是 MST 矛盾。故 $w(f)\leqslant w(e)$ ；
$f$ 跨越 $A,B$ ，故不在 $F-e$ 中。令 $F'=F-e+f$ ，它仍是扩展图的生成树，费用不超过 $F$ 。 $F$ 已最优，故费用相同，且 $F'$ 少用一条非 $T$ 的原图边。

反复交换即可得到同样最优、且原图边全在 $T$ 中的生成树。这个论证不怕 $A,B$ 里混着乡镇结点—— $u,v$ 仍是原有城市， $T$ 上连接它们的路径必然跨越这两个连通块。

两侧夹逼：只留 $T$ 后可选边变少，MST 不会更便宜；交换论证又说明完整扩展图至少有一棵 MST 落在缩减图里，所以也不会更贵。最优值不变。

每次 Kruskal 只扫 n-1 条原图边

于是固定 $S$ 时只需在

text

1原图 MST 的 n-1 条边 + 被选中乡镇到城市的边

上跑 Kruskal。实现上把全部乡镇边一次性排序，枚举 mask 时用双指针归并两条已排序序列：

原图 MST 边（ $n-1$ 条）；
当前 mask 允许的乡镇边（跳过未选乡镇的边）。

按边权从小到大尝试并查集合并，直到连通 $n+|mask|$ 个结点。

样例推演

样例 $1$ ： $n=4,m=4,k=2$ 。原图边 $(1,4,6),(2,3,7),(4,2,5),(4,3,4)$ ；乡镇 $0$ 改造费 $1$ ，建路费 $[1,8,2,4]$ ；乡镇 $1$ 改造费 $100$ ，建路费 $[1,3,2,4]$ 。

原图 MST 按边权取 $(4,3)=4$ 、 $(4,2)=5$ 、 $(1,4)=6$ ，共 $n-1=3$ 条，费用 $15$ （这也是一个乡镇都不选时的答案）。

枚举到 mask = {乡镇 0} 时，可选边是这 $3$ 条 MST 边加乡镇 $0$ 的 $4$ 条建路边，结点数 $4+1=5$ ，需要 $4$ 条边。按边权归并后 Kruskal 依次选：

text

1(0,1)=1, (0,3)=2, (4,3)=4, (4,2)=5

其中 $(4,t_0)=4$ 会被跳过，因为它的两端已在同一个连通块里。生成树费用 $12$ ，加上改造费 $1$ 得 $13$ ，与样例答案一致。

代码

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218/**
 * 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 23:04
 * update_at: 2026-10-01 23:04
 */
// main.cpp：先求原图 MST（百万条边只处理一次），再枚举乡镇子集，
// 在“MST 边 + 选中乡镇的连边”上跑 Kruskal 求最小生成树。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10005;   // n <= 1e4
const int MAXK = 11;      // k <= 10
const ll INF = 1LL << 62;

// 一条无向边：端点 u、v，修建或修复费用 w。
struct Edge {
    int u;
    int v;
    ll w;
};

// 按边权升序，Kruskal 需要。
bool cmp_edge(const Edge &x, const Edge &y) {
    return x.w < y.w;
}

int n, m, k;
ll town_cost[MAXK];         // town_cost[j]：把第 j 个乡镇城市化的固定费用
ll subset_cost[1 << MAXK];  // subset_cost[mask]：mask 中全部乡镇的城市化费用和

vector<Edge> original_edges; // 原有城市之间的全部 m 条边
vector<Edge> original_mst;   // 原图的一棵 MST，恰好 n-1 条边
vector<Edge> town_edges;     // 乡镇到原有城市的 n*k 条边

int fa[MAXN + MAXK];        // 并查集父亲
int dsu_size[MAXN + MAXK];  // 并查集连通块大小，用于按大小合并

// 每次 Kruskal 前把每个结点恢复成独立集合。
void init_dsu(int node_count) {
    for (int i = 1; i <= node_count; i++) {
        fa[i] = i;
        dsu_size[i] = 1;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find_root(fa[x]);
}

// 合并两个连通块，返回是否真的发生了合并。
bool merge_set(int u, int v) {
    int root_u = find_root(u);
    int root_v = find_root(v);
    if (root_u == root_v) {
        return false;
    }

    // 小树挂到大树上，与路径压缩配合，单次操作近乎常数。
    if (dsu_size[root_u] < dsu_size[root_v]) {
        swap(root_u, root_v);
    }
    fa[root_v] = root_u;
    dsu_size[root_u] += dsu_size[root_v];
    return true;
}

void read_input() {
    cin >> n >> m >> k;

    original_edges.reserve(m);
    town_edges.reserve(n * k);

    for (int i = 1; i <= m; i++) {
        Edge edge;
        cin >> edge.u >> edge.v >> edge.w;
        original_edges.push_back(edge);
    }

    for (int town = 0; town < k; town++) {
        cin >> town_cost[town];
        for (int city = 1; city <= n; city++) {
            Edge edge;
            edge.u = city;
            edge.v = n + town + 1;   // 乡镇 town 的结点编号是 n+town+1
            cin >> edge.w;
            town_edges.push_back(edge);
        }
    }
}

// 求只含原有城市时的一棵 MST。
// 交换论证保证：无论选了哪些乡镇，其他原图边都不必再看。
void build_original_mst() {
    sort(original_edges.begin(), original_edges.end(), cmp_edge);
    init_dsu(n);

    int cnt = original_edges.size();
    int mst_cnt = 0;
    for (int i = 0; i < cnt; i++) {
        const Edge &edge = original_edges[i];
        if (!merge_set(edge.u, edge.v)) {
            continue;   // 两端已连通，选它就会成环
        }

        original_mst.push_back(edge);
        mst_cnt++;
        if (mst_cnt == n - 1) {
            break;
        }
    }
}

// 用 lowbit 递推出每个乡镇子集的固定费用。
void build_subset_cost() {
    subset_cost[0] = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        ll sum = 0;
        for (int town = 0; town < k; town++) {
            if (mask & (1 << town)) {
                sum += town_cost[town];
            }
        }
        subset_cost[mask] = sum;
    }
}

// 这条乡镇边的另一端是否属于 mask 中被选中的乡镇。
bool town_edge_is_available(const Edge &edge, int mask) {
    int town = edge.v - n - 1;
    return (mask & (1 << town)) != 0;
}

// 在“原图 MST 边 + mask 允许的乡镇边”上跑一次 Kruskal。
ll solve_mask(int mask) {
    int selected_towns = __builtin_popcount(mask);
    // 扩展图有 n + selected_towns 个结点，生成树需要结点数减一条边。
    int need_edges = n + selected_towns - 1;
    int selected_edges = 0;
    ll answer = subset_cost[mask];

    // 并查集统一开到 n+k；未被 mask 选中的乡镇结点不会参与任何合并。
    init_dsu(n + k);

    // original_mst 与 town_edges 都已按边权排序，
    // 双指针取两边当前更小的边，就等价于把两组边归并后再跑 Kruskal。
    int original_pos = 0;
    int town_pos = 0;
    int town_total = town_edges.size();

    while (selected_edges < need_edges) {
        // 先跳过不属于选中乡镇的边，它们不在当前扩展图里。
        while (town_pos < town_total && !town_edge_is_available(town_edges[town_pos], mask)) {
            town_pos++;
        }

        bool take_original = false;
        if (original_pos < n - 1) {
            if (town_pos == town_total || original_mst[original_pos].w <= town_edges[town_pos].w) {
                take_original = true;
            }
        }

        Edge edge;
        if (take_original) {
            edge = original_mst[original_pos];
            original_pos++;
        } else {
            if (town_pos == town_total) {
                return INF;   // 边用尽仍没连通，实际不会发生
            }
            edge = town_edges[town_pos];
            town_pos++;
        }

        // 只有连通两个不同连通块时才真正选中这条边。
        if (merge_set(edge.u, edge.v)) {
            answer += edge.w;
            selected_edges++;
        }
    }

    return answer;
}

void solve() {
    // 百万条原图边只处理一次，之后每个 mask 只扫 n-1 条 MST 边。
    build_original_mst();
    sort(town_edges.begin(), town_edges.end(), cmp_edge);
    build_subset_cost();

    // k <= 10，直接枚举实际参与连通的乡镇集合。
    ll answer = INF;
    for (int mask = 0; mask < (1 << k); mask++) {
        ll current = solve_mask(mask);
        if (current < answer) {
            answer = current;
        }
    }

    cout << answer << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

原图边排序 $O(m\log m)$ ；
乡镇边排序 $O(nk\log(nk))$ ；
枚举 $2^k$ 个子集，每个扫 $O(nk)$ 条乡镇边与 $O(n)$ 条 MST 边，带一个近似常数的并查集。

总时间复杂度 $O(m\log m+nk\log(nk)+2^k\cdot nk\cdot\alpha(n+k))$ ，空间复杂度 $O(m+nk)$ 。

总结

这题不能只看到「枚举乡镇集合 + MST」，还要处理 $m=10^6$ 的瓶颈。

原图 MST 的替换性质是核心：不管选了哪些乡镇，原有城市之间都不需要非 MST 边。这样每个集合下的 Kruskal 就从扫描百万条原图边，变成只扫 $n-1$ 条 MST 边和少量乡镇边。

交换论证本身也是最小生成树题里最常用的一招：在最优解里拿一条非 MST 边，用 MST 上的路径找一条跨越断开的两个块、且权值不更大的边来替换，从而把最优解“搬”进缩减图。

本文的 main.cpp 已用直接重跑全量边的 brute.cpp 对拍 $1100$ 组随机数据（含稠密图与大量等权边），题面样例通过。

P14362 [CSP-S 2025] 道路修复

题目背景

由于评测机性能差异，本题时限提升 1 秒。

题目描述

C 国的交通系统由 $n$ 座城市与 $m$ 条连接两座城市的双向道路构成，第 $i$ ( $1 \leq i \leq m$ ) 条道路连接城市 $u_i$ 和 $v_i$ 。任意两座城市都能通过若干条道路相互到达。

然而，近期由于一场大地震，所有 $m$ 条道路都被破坏了，修复第 $i$ ( $1 \leq i \leq m$ ) 条道路的费用为 $w_i$ 。与此同时，C 国还有 $k$ 个准备进行城市化改造的乡镇。对于第 $j$ ( $1 \leq j \leq k$ ) 个乡镇，C 国对其进行城市化改造的费用为 $c_j$ 。在城市化改造完第 $j$ ( $1 \leq j \leq k$ ) 个乡镇后，可以在这个乡镇与原来的 $n$ 座城市间建造若干条道路，其中在它与第 $i$ ( $1 \leq i \leq n$ ) 座城市间建造一条道路的费用为 $a_{j,i}$ 。C 国可以在这 $k$ 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。

为尽快恢复城市间的交通，C 国政$ $府希望以最低的费用将**原有**的 $n$ 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 $n$ 座城市两两连通的最小费用。

输入格式

输入的第一行包含三个非负整数 $n, m, k$ ，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。

输入的第 $i+1$ ( $1 \leq i \leq m$ ) 行包含三个非负整数 $u_i, v_i, w_i$ ，表示第 $i$ 条道路连接的两座城市与修复该道路的费用。

输入的第 $j+m+1$ ( $1 \leq j \leq k$ ) 行包含 $n+1$ 个非负整数 $c_j, a_{j,1}, a_{j,2}, \ldots, a_{j,n}$ ，分别表示将第 $j$ 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。

输出格式

输出一行一个非负整数，表示将原有的 $n$ 座城市两两连通的最小费用。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
74 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4

输出 #1

text

说明/提示

【样例 1 解释】

C 国政$ $府可以选择修复第 $3$ 条和第 $4$ 条道路，然后将第 $1$ 个乡镇进行城市化改造，并建造它与第 $1,3$ 座城市间的道路，总费用为 $5 + 4 + 1 + 1 + 2 = 13$ 。可以证明，不存在比 $13$ 更小的费用能使原有的 $4$ 座城市两两连通。

【样例 2】

见选手目录下的 $\textbf{\textit{road/road2.in}}$ 与 $\textbf{\textit{road/road2.ans}}$ 。

该样例满足测试点 $11,12$ 的约束条件。

【样例 3】

见选手目录下的 $\textbf{\textit{road/road3.in}}$ 与 $\textbf{\textit{road/road3.ans}}$ 。

该样例满足测试点 $13,14$ 的约束条件。

【样例 4】

见选手目录下的 $\textbf{\textit{road/road4.in}}$ 与 $\textbf{\textit{road/road4.ans}}$ 。

该样例满足测试点 $15,16$ 的约束条件。

【数据范围】

对于所有测试数据，保证：

$1 \leq n \leq 10^4$ ， $1 \leq m \leq 10^6$ ， $0 \leq k \leq 10$ ；
对于所有 $1 \leq i \leq m$ ，均有 $1 \leq u_i, v_i \leq n$ ， $u_i \neq v_i$ 且 $0 \leq w_i \leq 10^9$ ；
对于所有 $1 \leq j \leq k$ ，均有 $0 \leq c_j \leq 10^9$ ；
对于所有 $1 \leq j \leq k$ ， $1 \leq i \leq n$ ，均有 $0 \leq a_{j,i} \leq 10^9$ ；
任意两座原有的城市都能通过若干条原有的道路相互到达。

::cute-table{tuack}

测试点编号	$n \leq$	$m \leq$	$k \leq$	特殊性质
$1 \sim 4$	$10^4$	$10^6$	$0$	无
$5, 6$	$10^3$	$10^5$	$5$	A
$7, 8$	^	^	^	无
$9, 10$	^	$10^6$	^	A
$11, 12$	^	^	^	无
$13, 14$	^	^	$10$	A
$15, 16$	^	^	^	无
$17, 18$	$10^4$	^	$5$	A
$19, 20$	^	^	^	无
$21 \sim 25$	^	^	$10$	^

特殊性质 A：对于所有 $1 \leq j \leq k$ ，均有 $c_j = 0$ 且均存在 $1 \leq i \leq n$ 满足 $a_{j,i} = 0$ 。