要求先用最少的边把全图连通，因此一定选 n-1 条边；再把这些边中的最大权值压到最小，直接按边权从小到大做 Kruskal，最后一条加入的边权就是答案。
OJ: luogu
题目 ID: P2330
难度:普及/提高-
标签:图论最小生成树并查集
日期: 2026-06-20 00:52
题意
要从原图里选出一些道路进行改造，满足：
- 这些道路能把所有点连通
- 在连通前提下，选的道路数量尽量少
- 在满足前两条后，选中道路里最大的分值尽量小
最后输出两件事：
- 最少需要改造多少条路
- 这种最优方案下，最大分值是多少
样例图
这张图把样例中的道路和分值画出来：
graph G {
1 -- 2 [label="3"];
1 -- 4 [label="5"];
2 -- 4 [label="7"];
2 -- 3 [label="6"];
3 -- 4 [label="8"];
}
如果选 1-2、1-4、2-3 这三条边，就已经能连通所有点。
这时一共选了 3 条边，也就是最少的 6，所以样例输出 3 6。
思路
先看一个按定义做的小数据暴力：
cpp
// brute.cpp：枚举所有 n-1 条边的方案，直接检查哪棵生成树的最大边最小。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
const int MAXM = 30;
const int INF = 1e9;
struct Edge {
int u, v, w;
} edges[MAXM];
int n, m;
int picked[MAXM];
int fa[MAXN];
int best_answer = INF;
void init_dsu() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find_root(int x) {
if (fa[x] == x) {
return x;
}
fa[x] = find_root(fa[x]);
return fa[x];
}
void unite(int x, int y) {
x = find_root(x);
y = find_root(y);
if (x != y) {
fa[x] = y;
}
}
void check_tree(int picked_cnt) {
if (picked_cnt != n - 1) {
return;
}
init_dsu();
int max_w = 0;
for (int i = 1; i <= picked_cnt; i++) {
Edge &e = edges[picked[i]];
unite(e.u, e.v);
max_w = max(max_w, e.w);
}
int root = find_root(1);
for (int i = 2; i <= n; i++) {
if (find_root(i) != root) {
return;
}
}
best_answer = min(best_answer, max_w);
}
void dfs(int pos, int picked_cnt) {
if (picked_cnt > n - 1) {
return;
}
if (pos > m) {
check_tree(picked_cnt);
return;
}
picked[picked_cnt + 1] = pos;
dfs(pos + 1, picked_cnt + 1);
dfs(pos + 1, picked_cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
dfs(1, 0);
cout << n - 1 << ' ' << best_answer << '\n';
return 0;
}暴力直接枚举所有恰好选
- 看它能不能把所有点连起来
- 如果能，就统计这组边里的最大分值
- 取最小值
这个思路直观，但边多时当然不行。
先看条件 2：“在满足连通的情况下，改造的道路尽量少。”
连通一个 n 个点的无向图，最少只需要
接着看条件 3：在所有生成树里，让最大边权尽量小。
这题直接按边权从小到大做 Kruskal 就行：
- 把所有边按分值升序排序
- 能连通两个不同连通块的边就选
- 直到选满
条边为止
为什么最后一条加入的边权就是最优答案？
因为 Kruskal 是按从小到大的顺序在“尽量早”地把图连起来。
如果在选到某条边权 w 时，图才第一次完全连通，那么说明：
- 所有边权
< w的边，不足以让全图连通
所以任何满足要求的方案，最大边权都不可能小于 w。
而 Kruskal 又确实在边权 w 时做到了连通，因此这个 w 就是最小可能值。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const int MAXM = 8005;
struct Edge {
int u, v, w;
bool operator<(const Edge &other) const {
return w < other.w;
}
} edges[MAXM];
int n, m;
int fa[MAXN];
void init_dsu(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find_root(int x) {
if (fa[x] == x) {
return x;
}
fa[x] = find_root(fa[x]);
return fa[x];
}
bool unite(int x, int y) {
x = find_root(x);
y = find_root(y);
if (x == y) {
return false;
}
fa[x] = y;
return true;
}
int kruskal_answer() {
sort(edges + 1, edges + m + 1);
init_dsu(n);
int used = 0;
int max_w = 0;
for (int i = 1; i <= m; i++) {
if (!unite(edges[i].u, edges[i].v)) {
continue;
}
used++;
max_w = max(max_w, edges[i].w);
if (used == n - 1) {
break;
}
}
return max_w;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
cout << n - 1 << ' ' << kruskal_answer() << '\n';
return 0;
}复杂度
设点数为 n，边数为 m。
Kruskal 的复杂度是：
- 排序
- 并查集合并
总时间复杂度
总结
这题本质上是在生成树里求“最小瓶颈”。但不需要额外记复杂性质，直接抓住 Kruskal 的过程就够了：按边权从小到大连通全图时，最后一条被选中的边，就是最小可能的最大边。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
