[CSP-S 2025] 道路修复

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

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

OJ: luogu

题目 ID: P14362

难度:提高+/省选-

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

日期: 2026-06-22 19:46

题意

有 n 座原有城市和 m 条原有城市之间的双向道路。所有道路都坏了，修复第 i 条道路费用为 w_i。

另外有 k 个乡镇，k <= 10。可以选择任意多个乡镇进行城市化改造。选择第 j 个乡镇要先支付 c_j，之后可以建造它到任意原有城市的道路，连接到第 i 座城市的费用为 a[j][i]。

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

思路

先看一个可以直接验证想法的朴素解：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXK = 5;
const long long INF = (1LL << 62);

struct Edge {
    int u;
    int v;
    long long w;
};

int n, m, k;
long long city_cost[MAXK];
long long a[MAXK][MAXN];
vector<Edge> original_edges;

int fa[MAXN + MAXK], sz[MAXN + MAXK];

bool cmp_edge(const Edge &x, const Edge &y) {
    return x.w < y.w;
}

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;
}

long long solve_mask(int mask) {
    vector<Edge> edges = original_edges;
    long long cost = 0;
    int selected_towns = 0;

    for (int j = 0; j < k; j++) {
        if ((mask & (1 << j)) == 0) {
            continue;
        }
        selected_towns++;
        cost += city_cost[j];
        for (int i = 1; i <= n; i++) {
            Edge e;
            e.u = i;
            e.v = n + j + 1;
            e.w = 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;
    for (int i = 0; i < (int)edges.size() && 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;
    original_edges.clear();
    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 >> city_cost[j];
        for (int i = 1; i <= n; i++) {
            cin >> a[j][i];
        }
    }

    long long ans = INF;
    for (int mask = 0; mask < (1 << k); mask++) {
        ans = min(ans, solve_mask(mask));
    }

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

因为 k <= 10，可以枚举实际参与连通的乡镇集合 S。

这里先处理一个细节：如果某个已城市化的乡镇没有连接任何道路，那么它对原有城市的连通性没有贡献。取消这个乡镇的城市化不会增加费用，也不会破坏连通性。因此，一定存在一个最优方案，其中每个被选择的乡镇都至少通过一条新道路连接到某座原有城市。

乡镇只能与原有城市相连，所以这些实际参与连通的乡镇一定和所有原有城市处于同一个连通块。固定集合 S 后，把原有城市和 S 中的乡镇放在同一张扩展图里，边包括：

原有城市之间的 m 条修复边；
被选中乡镇到每个原有城市的建造边。

所有边权都非负，因此可以删去连通方案中的环而不增加费用。于是，固定 S 后的最小连接费用，就是这张扩展图的最小生成树费用，再加上 S 中乡镇的改造费用。

直接这么做的问题在于 m 最大有 10^6，如果每个乡镇集合都重新处理所有原图边，会非常慢。

真正需要优化的是反复处理的原图边。事实上，原有城市之间的边只需要保留原图的一棵 MST。

为什么原图边只需保留一棵 MST

只由原有城市和原有道路组成的图记为 G，先求出 G 的一棵 MST，记为 T。固定乡镇集合 S 后，完整扩展图的一棵最优生成树记为 F。

我们要证明的不是“每棵 F 都只使用 T 中的原图边”，而是：至少存在一棵同样优的 F，它使用的原图边全部属于 T。这样，删除其他原图边就不会改变最优答案。

交换过程可以先概括为：

text

1
2
3F 删除 e -> 分成 A、B 两个连通块
T 上的 u-v 路径 -> 选一条跨越 A、B 的边 f
F - e + f -> 仍是一棵生成树，且 w(f) <= w(e)

这里不是把一条边 e 换成整条 u-v 路径；我们只从路径上取一条跨越两个连通块的边 f。这条路径的作用，是保证这样的 f 一定存在。

下面严格证明这个交换过程。假设 F 使用了一条不属于 T 的原图边 e=(u,v,w)：

从树 F 中删去 e，F 会分成两个连通块 A 和 B。不妨设 u 在 A 中，v 在 B 中。
在树 T 中，u 到 v 有唯一一条路径。这条路径从 A 中的 u 走到 B 中的 v，因此其中至少有一条边 f 跨越 A、B。
T 的这条 u-v 路径上，每条边的边权都不超过 w。否则，若路径上存在一条更重的边 x，用 e 替换 x 就会得到一棵比 T 更小的原图生成树，与 T 是 MST 矛盾。因此 w(f) <= w(e)。
边 f 跨越 A、B，所以它不可能已经存在于 F-e 中。用 f 重新连接 A、B，得到 F' = F-e+f。F' 仍是一棵扩展图的生成树，并且费用不超过 F。由于 F 已经最优，F' 的费用必然与 F 相同；同时，F' 比 F 少使用一条不属于 T 的原图边。

不断执行这个交换，最终会得到一棵同样最优的扩展图生成树，其中所有原图边都属于 T。这个论证不怕连通块 A、B 中含有乡镇节点：u、v 仍是原有城市，而 T 中连接它们的路径仍然必定跨越这两个连通块。

只保留 T 后，可选边变少，所以新图的 MST 不可能比完整扩展图更便宜；另一方面，上面的交换证明说明完整扩展图至少有一棵 MST 完全存在于新图中，所以新图也不会更贵。两边结合，最优值不变。

所以固定乡镇集合 S 时，只需要在：

text

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

上跑 Kruskal。

实现时，把所有乡镇到城市的边统一排序。枚举 mask 表示实际参与连通的乡镇集合，每次用两个指针归并扫描：

原图 MST 边；
当前 mask 允许的乡镇边。

按边权从小到大尝试并查集合并，直到连通 n + popcount(mask) 个节点。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXK = 10;
const long long INF = (1LL << 62);

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

    // rbook 的 Kruskal 模板通过 operator< 按边权排序。
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

int n, m, k;
long long town_cost[MAXK];             // town_cost[j]：城市化第 j 个乡镇的固定费用
long long 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;
            // 原有城市编号为 1..n，乡镇 town 的节点编号为 n+town+1。
            edge.v = n + town + 1;
            cin >> edge.w;
            town_edges.push_back(edge);
        }
    }
}

// 使用 rbook 的标准 Kruskal 思路，求出只含原有城市时的一棵 MST。
// 题解中的交换证明保证：以后无论选择哪些乡镇，其他原图边都可以删去。
void build_original_mst() {
    sort(original_edges.begin(), original_edges.end());
    init_dsu(n);

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

        original_mst.push_back(edge);
        if ((int)original_mst.size() == n - 1) {
            break;
        }
    }
}

// 用 lowbit 递推每个乡镇集合的固定费用。
void build_subset_cost() {
    subset_cost[0] = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        int lowbit = mask & -mask;
        int town = 0;
        while ((1 << town) != lowbit) {
            town++;
        }
        // 去掉最低位的乡镇，再加回这个乡镇的城市化费用。
        subset_cost[mask] = subset_cost[mask ^ lowbit] + town_cost[town];
    }
}

// 从乡镇节点编号还原乡镇下标，判断这条边能否出现在当前 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。
long long solve_mask(int mask) {
    int selected_towns = __builtin_popcount((unsigned)mask);
    // 当前扩展图有 n+selected_towns 个有效节点，生成树需要“点数-1”条边。
    int need_edges = n + selected_towns - 1;
    int selected_edges = 0;
    long long answer = subset_cost[mask];

    // 数组统一初始化到 n+k；未被 mask 选择的乡镇节点始终不会参与合并。
    init_dsu(n + k);

    int original_pos = 0;
    int town_pos = 0;

    // original_mst 与 town_edges 都已按边权排序。
    // 用双指针取两个序列当前更小的边，就等价于把两组边合并后再跑 Kruskal。
    while (selected_edges < need_edges) {
        // 跳过属于未选乡镇的边，它们不在当前扩展图中。
        while (town_pos < (int)town_edges.size() &&
               !town_edge_is_available(town_edges[town_pos], mask)) {
            town_pos++;
        }

        // 比较两组序列的队首，决定 Kruskal 下一条检查哪条边。
        bool take_original = false;
        if (original_pos < (int)original_mst.size()) {
            if (town_pos == (int)town_edges.size() ||
                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 == (int)town_edges.size()) {
                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());
    build_subset_cost();

    long long answer = INF;
    // k<=10，直接枚举哪些乡镇实际参与连通。
    for (int mask = 0; mask < (1 << k); mask++) {
        answer = min(answer, solve_mask(mask));
    }

    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 很大的瓶颈。

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

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$ 。