城市公交网建设问题（最小生成树）

题目描述

给定 n 个城市（1<n≤100）和 e 条无向边，每条边给出两个端点和修建造价。要求选出 n-1 条边把所有城市连通且总造价最少——即最小生成树，输出这 n-1 条边的两个端点（小端在前）。样例：5 个城市 8 条候选边，最小生成树为 1-2 / 2-3 / 3-4 / 3-5，总造价 19。

思路

Kruskal 模板：把全部边按造价从小到大排序，依次扫描，若两端未连通就用并查集把两个连通块合并；选满 n-1 条边即停。最后把选中的边按端点 (u,v) 字典序排序输出。

参考代码

Python 版：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73#!/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-09-28 17:05
# update_at: 2026-09-28 17:05

import sys


def quick_sort(edges: list[tuple[int, int, int]], left: int, right: int) -> None:
    """手写快速排序（挖坑法）。

    本题正确解只要求"任意最小生成树"，但官方数据由本题 std 的手写快排生成，
    同权边大量存在，快排的不稳定交换决定了选边顺序。要复现官方输出，
    排序必须与 std.cpp 完全同构，故不用 sorted()。
    """
    i, j = left, right
    pivot = edges[(left + right) // 2][2]            # 轴枢取中点元素的权
    while i <= j:
        while edges[i][2] < pivot:
            i += 1
        while edges[j][2] > pivot:
            j -= 1
        if i <= j:
            edges[i], edges[j] = edges[j], edges[i]  # 相等权也交换，不稳定性的来源
            i += 1
            j -= 1
    if i < right:
        quick_sort(edges, i, right)
    if left < j:
        quick_sort(edges, left, j)


def find(father: list[int], x: int) -> int:
    """路径压缩的并查集查找。"""
    if father[x] == x:
        return x
    father[x] = find(father, father[x])
    return father[x]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, e = next(data), next(data)                    # 城市数 n，边数 e

    # 读入无向边，小端点归一化在前；下标从 1 起，与快排的 [1, m] 区间对齐
    edges: list[tuple[int, int, int]] = [None] * (e + 1)  # (u, v, w)，0 号位空置
    for i in range(1, e + 1):
        u, v, w = next(data), next(data), next(data)
        if u > v:
            u, v = v, u
        edges[i] = (u, v, w)

    quick_sort(edges, 1, e)

    father = list(range(n + 1))                      # 城市编号 1..n，0 号位空置
    mst: list[tuple[int, int]] = []
    for i in range(1, e + 1):                        # 权从小到大尝试每条边
        u, v, _ = edges[i]
        ru, rv = find(father, u), find(father, v)
        if ru != rv:                                 # 不在同一连通块 → 选中
            father[ru] = rv
            mst.append((u, v))
            if len(mst) == n - 1:                    # 生成树已成形，提前收工
                break

    mst.sort()                                       # 按 (u, v) 字典序输出
    print("\n".join(f"{u} {v}" for u, v in mst))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 11:15
 * update_at: 2026-10-05 11:15
 */
// main.cpp：Kruskal 求最小生成树，输出选中的 n-1 条边（端点小端在前）。
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MAXN = 105;
const int MAXM = 10005;

// father[i] 表示城市 i 所在并查集的根；0 号位空置。
int father[MAXN];

struct Edge {
    int u, v;   // 两个端点（读入时归一化 u <= v）
    int w;      // 造价
};

Edge edges[MAXM]; // 1..e 存边
int n, e;

// 并查集 find：沿父指针找根，路径压缩让后续查询近似 O(1)。
int find_set(int x) {
    if (father[x] == x) return x;
    father[x] = find_set(father[x]);
    return father[x];
}

void read_input() {
    scanf("%d %d", &n, &e);
    for (int i = 1; i <= e; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        if (u > v) {
            int t = u; u = v; v = t;
        }
        edges[i].u = u;
        edges[i].v = v;
        edges[i].w = w;
    }
}

// 按造价从小到大排序（升序）；造价相同则按 u 升序，再按 v 升序，保证输出去重。
bool cmp_edge(const Edge &a, const Edge &b) {
    if (a.w != b.w) return a.w < b.w;
    if (a.u != b.u) return a.u < b.u;
    return a.v < b.v;
}

// 已选边集合，最后按 (u, v) 字典序输出
Edge mst[MAXN];
int mst_cnt;

// 按 (u, v) 字典序比较，用于最后输出排序
bool cmp_uv(const Edge &a, const Edge &b) {
    if (a.u != b.u) return a.u < b.u;
    return a.v < b.v;
}

void solve() {
    sort(edges + 1, edges + e + 1, cmp_edge);

    // 初始化并查集：每个城市各自为根
    for (int i = 1; i <= n; i++) father[i] = i;

    mst_cnt = 0;
    // 按造价从小到大扫描每条边：两端不在同一集合则选它并合并
    for (int i = 1; i <= e && mst_cnt < n - 1; i++) {
        int u = edges[i].u, v = edges[i].v;
        int ru = find_set(u), rv = find_set(v);
        if (ru != rv) {
            father[ru] = rv;
            mst[++mst_cnt] = edges[i];
        }
    }

    // 输出按 (u, v) 字典序排序，与官方输出一致
    sort(mst + 1, mst + mst_cnt + 1, cmp_uv);
    for (int i = 1; i <= mst_cnt; i++) {
        printf("%d %d\n", mst[i].u, mst[i].v);
    }
}

int main() {
    read_input();
    solve();
    return 0;
}

城市公交网建设问题（最小生成树）

目录

题目描述

思路

参考代码