P2330 繁忙的都市

思路

最小生成樹一定會是最小瓶頸樹，證明略。
那瓶頸樹是什麼呢？它是一個要連通所有節點的圖，並且這顆樹的最大邊數值盡可能小。
最小生成樹一定是連接所有節點的。而在選擇邊時，也都是選最小的 $n-1$ 條邊，
最大邊的數值以直覺來看，那當然就是最小的。

以這題為例，要想建立出連接所有交叉路口的道路，改造的道路盡量少，並且改的道路分值盡量小。
根據上面提到的生成樹跟瓶頸樹，我們知道這是要找瓶頸樹，而最小生成樹滿足瓶頸樹要求，這就成了找最小生成樹的題目。

程式碼

最小生成樹 Kruskal

#include <iostream>
#include <array>
#include <numeric>
#include <algorithm>
using namespace std;
const int MAXN = 301;
const int MAXM = 8001;
int n, m;
int parent[MAXN];
array<int, 3> edges[MAXM]; // 為了排序，用 array
int find(int x) {
    if(parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}
void unite(int x, int y) {
    parent[find(x)] = parent[find(y)];
}
void build() {
    iota(parent, parent + n, 0);
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    build();
    for(int i = 0; i < m; i++) {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }
    sort(edges, edges + m, [&](const auto& a, const auto& b){ // 根據分值排序
        return a[2] < b[2];
    });
    int edgeCnt = 0;
    for(int i = 0; i < m; i++) {
        auto& edge = edges[i];
        if(!isSameSet(edge[0], edge[1])) {
            unite(edge[0], edge[1]);
            if(++edgeCnt == n - 1) {
                cout << edgeCnt << " " << edge[2]; // 選到的最後一條邊，它對應的分值一定是最大的，不需要暫存。
                break;
            }
        }
    }
}

複雜度分析

• 時間複雜度：$O(m\log{m})$
• 空間複雜度：$O(n+m)$