【題解】Codeforces Gym 100712F Travelling Salesman

【題目敘述】https://codeforces.com/gym/100712/attachments
【解題想法】最大邊最小的生成樹 (Minimum Bottleneck Spanning Tree, MBST)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct e{
    int x, y, cost;
};
bool cmp(e x, e y){
    return x.cost < y.cost;
}
int p[100005], t, n, m, j, k, c, ans;
vector <e> v;
int find(int a){
    if (p[a] == a) return a;
    else {
        p[a] = find(p[a]);
        return p[a];
    }
}
int main() {
    cin >> t;
    while (t--){
        cin >> n >> m;
        ans = 0;
        v.clear();
        for (int i = 1; i <= n; i++){
            p[i] = i;
        }
        for (int i = 0; i < m; i++){
            cin >> j >> k >> c;
            v.push_back({j, k, c});
        }
        sort(v.begin(), v.end(), cmp);
        for (e tmp:v){
            j = find(tmp.x);
            k = find(tmp.y);
            if (j == k) continue;
            p[k] = j;
            ans = max(ans, tmp.cost);
            n--;
            if (n == 1) break;
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends