[CSP-S 2025] 道路修复

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

枚举被城市化的乡镇集合，并用原图 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，可以枚举每个乡镇是否城市化。固定一个乡镇集合后，把原有城市和这些乡镇放在同一张图里，边包括：

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

这时最小连接费用就是这张扩展图的最小生成树费用，再加上选中乡镇的改造费用。

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

关键优化：原有城市之间的边，只需要保留原图的一棵 MST。

先在原有 n 座城市和 m 条道路上求出一棵 MST，记为 T。对于任意不在 T 里的原图边 e=(u,v,w)，T 中 u 到 v 的路径上不会有比 w 更大的边。否则可以用 e 替换那条更大的边，得到更小的生成树，矛盾。

因此，如果某个固定乡镇集合的方案用了非 MST 原图边 e，就可以用 T 上连接 u,v 的路径中的边替换它，费用不会增加。乡镇节点只连接原有城市，不会破坏这个替换过程。

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

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

const int MAXN = 10005;
const int MAXK = 10;
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 subset_cost[1 << MAXK];
vector<Edge> original_edges;
vector<Edge> mst_edges;
vector<Edge> town_edges;

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

bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.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;
}

void build_original_mst() {
    sort(original_edges.begin(), original_edges.end(), cmp_edge);
    init_dsu(n);

    for (int i = 0; i < (int)original_edges.size(); i++) {
        Edge e = original_edges[i];
        if (unite_set(e.u, e.v)) {
            mst_edges.push_back(e);
            if ((int)mst_edges.size() == n - 1) {
                break;
            }
        }
    }
}

void build_subset_cost() {
    int total_mask = 1 << k;
    subset_cost[0] = 0;
    for (int mask = 1; mask < total_mask; mask++) {
        int lowbit = mask & -mask;
        int id = 0;
        while ((1 << id) != lowbit) {
            id++;
        }
        subset_cost[mask] = subset_cost[mask ^ lowbit] + city_cost[id];
    }
}

bool edge_allowed_by_mask(const Edge &e, int mask) {
    int town_id = e.v - n - 1;
    return (mask & (1 << town_id)) != 0;
}

long long kruskal_with_towns(int mask) {
    int selected_towns = __builtin_popcount((unsigned)mask);
    int need_edges = n + selected_towns - 1;
    int picked = 0;
    long long cost = subset_cost[mask];

    init_dsu(n + k);

    int p1 = 0;
    int p2 = 0;
    while (picked < need_edges) {
        while (p2 < (int)town_edges.size() && !edge_allowed_by_mask(town_edges[p2], mask)) {
            p2++;
        }

        bool use_original = false;
        if (p1 < (int)mst_edges.size()) {
            if (p2 == (int)town_edges.size() || mst_edges[p1].w <= town_edges[p2].w) {
                use_original = true;
            }
        }

        Edge e;
        if (use_original) {
            e = mst_edges[p1];
            p1++;
        } else {
            if (p2 == (int)town_edges.size()) {
                return INF;
            }
            e = town_edges[p2];
            p2++;
        }

        if (unite_set(e.u, e.v)) {
            cost += e.w;
            picked++;
        }
    }

    return cost;
}

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

    cin >> n >> m >> k;
    original_edges.reserve(m);
    town_edges.reserve(n * 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 >> city_cost[j];
        for (int i = 1; i <= n; i++) {
            long long x;
            cin >> x;
            Edge e;
            e.u = i;
            e.v = n + j + 1;
            e.w = x;
            town_edges.push_back(e);
        }
    }

    build_original_mst();
    sort(town_edges.begin(), town_edges.end(), cmp_edge);
    build_subset_cost();

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

    cout << ans << '\n';
    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$ 。