题解：繁忙都市道路改造问题

一、题目背景

给定一个有 (n) 个交叉路口和 (m) 条道路的城市，道路是双向且连通所有路口，每条道路有一个分值代表繁忙程度。市长希望在改造道路时，满足以下条件：改造的道路能连通所有路口；改造道路数量最少；改造道路中分值的最大值尽可能小。需要找出满足条件的改造方案，输出改造道路的数量以及其中分值最大的道路的分值。

二、解题思路

本题可使用最小生成树算法（如Kruskal算法）来解决。因为要使改造的道路能连通所有路口且数量最少，这就是求一个连通图的生成树；而要使改造道路中分值的最大值尽可能小，就是求最小生成树中最大的边权。

Kruskal算法的基本步骤如下：
1. 定义一个结构体来存储道路的信息，包括两个端点和分值。
2. 读取交叉路口数量 (n) 和道路数量 (m)，以及每条道路的信息，将其存储到结构体数组中。
3. 对所有道路按照分值从小到大进行排序。
4. 初始化并查集，用于判断两个交叉路口是否在同一个连通分量中。
5. 遍历排序后的道路数组，对于两个端点不在同一个连通分量中的道路，将其加入最小生成树，并合并两个端点所在的连通分量，同时记录加入的道路数量和当前道路的分值（用于更新最大分值）。
6. 当加入的道路数量达到 (n - 1) 时（即构成了生成树），结束遍历，输出道路数量和最大分值。

三、代码示例（以C++ 为例）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310, M = 8010;

// 定义道路结构体
struct Edge {
    int a, b, c;
    bool operator<(const Edge &t) const {
        return c < t.c;
    }
};

Edge edges[M];
int p[N];

// 并查集查找函数
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n, m;
    cin >> n >> m;

    // 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i;

    // 读取道路信息
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    // 对道路按分值排序
    sort(edges, edges + m);

    int res = 0, max_c = 0;  // res记录选取道路数量，max_c记录最大分值
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, c = edges[i].c;
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
            res++;
            max_c = c;
            if (res == n - 1) break;
        }
    }

    // 输出结果
    cout << res << " " << max_c << endl;

    return 0;
}

四、代码逐段分析

1. 头文件和全局变量

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310, M = 8010;

// 定义道路结构体
struct Edge {
    int a, b, c;
    bool operator<(const Edge &t) const {
        return c < t.c;
    }
};

Edge edges[M];
int p[N];

- 引入头文件，`iostream` 用于输入输出，`algorithm` 用于排序等操作。
- 定义常量 `N` 和 `M` 分别表示交叉路口数量和道路数量的上限。
- 定义 `Edge` 结构体存储道路的两个端点 `a`、`b` 和分值 `c`，并重载 `<` 运算符，方便对道路按照分值进行排序。
- `Edge edges[M]` 用于存储所有道路的信息。
- `int p[N]` 用于实现并查集，存储每个交叉路口的父节点。

1. 并查集查找函数

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

该函数用于在并查集中查找交叉路口 x 的根节点，同时进行路径压缩，提高后续查找效率。
3. main 函数

int main() {
    int n, m;
    cin >> n >> m;

    // 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i;

    // 读取道路信息
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    // 对道路按分值排序
    sort(edges, edges + m);

    int res = 0, max_c = 0;  // res记录选取道路数量，max_c记录最大分值
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, c = edges[i].c;
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
            res++;
            max_c = c;
            if (res == n - 1) break;
        }
    }

    // 输出结果
    cout << res << " " << max_c << endl;

    return 0;
}

- 读取交叉路口数量 `n` 和道路数量 `m`。
- 初始化并查集，使每个交叉路口的父节点为自身。
- 读取每条道路的信息，存储到 `edges` 数组中。
- 对所有道路按照分值从小到大排序。
- 遍历排序后的道路数组，对于两个端点不在同一个连通分量中的道路，将其加入最小生成树（合并连通分量），同时更新选取道路数量 `res` 和最大分值 `max_c`，当选取道路数量达到 `n - 1` 时，结束遍历。
- 输出选取道路的数量和最大分值。

五、时间复杂度和空间复杂度分析

1. 时间复杂度：排序道路的时间复杂度为 (O(m \log m))，其中 (m) 是道路数量。遍历道路并进行并查集操作的时间复杂度为 (O(m \alpha(n)))，(\alpha(n)) 是阿克曼函数的反函数，在实际应用中可近似看作常数。所以总体时间复杂度为 (O(m \log m))。
2. 空间复杂度：存储道路信息需要 (O(m)) 的空间，存储并查集需要 (O(n)) 的空间，所以总体空间复杂度为 (O(m + n))。

希望这份题解能帮助你理解这道题的解题思路和实现方法。如果有任何疑问，欢迎随时提问。