繁忙的都市(city)

形式化题目

给定一个包含 $n$ 个节点和 $m$ 条带权双向边的连通无向图。需要从中选出一个边的子集，满足：

这些边能把所有的 $n$ 个节点直接或间接地连通（保证整张图连通）。
在满足条件 1 的前提下，选出的边数最少。
在满足条件 1 和 2 的前提下，选出的边的最大权值尽可能小。

请求出最少需要选取的边数，以及在这个前提下，所有选取边中的最大权值。

数据范围：

$1 \le n \le 300$
$1 \le m \le \frac{n(n-1)}{2}$
$1 \le c \le 10000$

正解

思路

本题需要满足三个条件，我们逐一分析：

连通所有节点：即选出的边集能够构成原图的一个连通子图。
边数最少：将 $n$ 个节点连通，最少需要的边数是 $n-1$ 。这意味着我们选出的边集实际上构成了一棵生成树（Spanning Tree）。
最大边权最小：要求在这棵生成树中，最大权值的边尽可能小。这一性质被称为“最小瓶颈生成树”。

根据最小生成树（MST）的性质，图的任意一棵最小生成树必然也是一棵最小瓶颈生成树。换言之，我们只需要使用 Kruskal 算法求出原图的最小生成树即可。

在 Kruskal 算法中：

将所有边按权值升序排序。
利用并查集维护节点的连通性，从前往后遍历排序后的边。
若当前边的两端点不在同一个连通块内，则将它们合并，并选中这条边。
当选中第 $n-1$ 条边时，所有的点已连通。由于我们是按边权升序遍历的，最后加入的那条边的权值就是整棵生成树的最大边权，它即为连通全图不可绕过的“瓶颈”。
最终输出 $n-1$ 和最后那条被选中边的权值。

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58#!/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-10-08 19:59
# update_at: 2026-10-08 19:59

import sys

type EdgeList = list[tuple[int, int, int]]  # 边表，每项是 (边权 w, 端点 u, 端点 v)，已按 w 升序


def find_root(parent: list[int], x: int) -> int:
    """并查集找根，带路径压缩（迭代版，不依赖递归深度）。"""
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


def min_bottleneck(edges: EdgeList, n: int) -> tuple[int, int]:
    """Kruskal 求最小生成树，返回 (选中的边数, 选中边的最大边权)。

    边表已按边权升序排好；MST 同时是最小瓶颈生成树，所以最后加入的那条边的
    边权就是「连通全图所需的最大边权」的最小值。
    """
    parent = list(range(n + 1))
    chosen = 0      # 已选边数，连通全图后恰好是 n-1
    bottleneck = 0  # 已选边中的最大边权
    for w, u, v in edges:
        root_u, root_v = find_root(parent, u), find_root(parent, v)
        if root_u == root_v:
            continue
        parent[root_u] = root_v
        chosen += 1
        bottleneck = w  # 边已升序，最后加入的边权就是生成树的最大边权
        if chosen == n - 1:
            break           # 已经连通，后面的边权只会更大
    return chosen, bottleneck


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 读入顺序是 (u, v, w)，重排成 (w, u, v) 后整体排序，直接得到按边权升序的边表
    edges: EdgeList = []
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        edges.append((w, u, v))
    edges.sort()

    chosen, bottleneck = min_bottleneck(edges, n)
    print(chosen, bottleneck)


if __name__ == "__main__":
    solve()

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/**
 * 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-08 20:00
 * update_at: 2026-10-08 20:00
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 305;    // n <= 300，多留几个
const int MAXM = 50000;  // m <= n(n-1)/2 = 44850

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

Edge edge[MAXM];       // 边表，1..m 存放题目给的 m 条边
ll parent_node[MAXN];  // 并查集父节点，parent_node[i] == i 表示 i 是所在连通块的根

// 按边权升序，供 sort 使用（不用 lambda）
bool cmp_edge(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

// 路径压缩查找 x 所在连通块的根
ll find_set(ll x) {
    while (parent_node[x] != x) {
        parent_node[x] = parent_node[parent_node[x]];
        x = parent_node[x];
    }
    return x;
}

void solve() {
    ll n, m;
    if (!(cin >> n >> m)) {
        return;
    }
    for (ll i = 1; i <= m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }

    // Kruskal：边权升序贪心，能连通就选
    sort(edge + 1, edge + m + 1, cmp_edge);

    for (ll i = 1; i <= n; i++) {
        parent_node[i] = i;
    }

    ll chosen = 0;     // 已选边数，连通后恰好是 n-1
    ll bottleneck = 0; // 已选边中的最大边权
    for (ll i = 1; i <= m; i++) {
        ll root_u = find_set(edge[i].u);
        ll root_v = find_set(edge[i].v);
        if (root_u == root_v) {
            continue;
        }
        parent_node[root_u] = root_v;
        chosen++;
        bottleneck = edge[i].w; // 边已升序，最后加入的边权就是最大值，无需再比较
        if (chosen == n - 1) {
            break;
        }
    }

    cout << chosen << " " << bottleneck << "\n";
}

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

    solve();

    return 0;
}

复杂度

时间复杂度： $O(m \log m)$ 。算法的耗时主要在对所有边按边权排序上。后续遍历每条边并使用并查集维护连通性的过程，通过路径压缩/折半，时间开销几乎为线性的，整体时间复杂度为 $O(m \log m)$ 。
空间复杂度： $O(n + m)$ 。需要存储 $m$ 条边的信息，以及并查集的父节点数组，大小为 $O(n)$ 。

总结

题意提炼：选出 $n-1$ 条边将整张图连通，并使“耗时最长的那条道路分值尽量小”，这等价于最小化最大边权（即求最小瓶颈），而不是要求最小化所有被选边的总权值和。
MST 的最小瓶颈性质：最小生成树（MST）必然同时是一棵最小瓶颈生成树。这是一个非常重要的结论。
- 证明（阈值视角）：假设 $W^*$ 是能够连通全图的最小阈值，那么只保留边权 $\le W^*$ 的边时，图刚好连通；若保留 $\le W^*-\epsilon$ 的边，图就不连通。Kruskal 算法按照权值从小到大加边，必然是在考虑边权为 $W^*$ 的边时才首次连通整张图，所以它求得的最大边权就是 $W^*$ 。
- 证明（割性质/反证）：假设存在某棵生成树 $T$ ，其最大边权小于 MST。当我们向 $T$ 中加入 MST 里权值最大的那条“瓶颈边”时，必定会形成一个环。在这个环上，至少存在一条属于 $T$ 的边的权值小于这条瓶颈边。根据割的性质，我们可以用 $T$ 中那条较小的边替换掉这条瓶颈边，从而得到一个总权值更小、或者同样权值但字典序更优的生成树，这与 MST 已经是最小生成树的前提矛盾。
算法细节：
- 边存储采用 struct Edge 数组，在 C++ 实现中摒弃了平行的数组结构；并通过普通的比较函数 cmp_edge 实现升序排序。
- 在 Kruskal 并查集的查找操作 find_set 中，应使用迭代式路径压缩（折半） parent_node[x] = parent_node[parent_node[x]]，避免当点数 $n$ 或路径较长时，递归形式的查找发生爆栈。
- 在记录最大权值时，由于边已经是升序排列的，最后一条被选入的边自然就是当前已选集合中的最大权值，因此可以直接赋值 bottleneck = edge[i].w，无需使用 max 进行冗余的比较累积。
数据与边界：
- 官方评测数据的输出文件（.OUT）行尾采用的是 CRLF（Windows 风格换行），但这不影响判定（评测归一化后等同于单换行 LF）。
- 代码输出格式为两个以空格分隔的整数，并辅以单换行。
- 极端边界情况：当 $n=1, m=0$ 时，程序将输出 0 0，即无需选边，无改造瓶颈。即便在图不连通的输入下，选出已能构成的极大森林边数后循环就会正常终止，不会产生死循环。

目录

形式化题目

正解

思路

代码

复杂度

总结