P2330 [SCOI2005]繁忙的都市

Link

题解

最小生成树

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
const int maxn = 300 + 10;
using namespace std;

int fa[maxn];

typedef struct Edge {
    int u, v, c;
    Edge(int x, int y, int z) :u(x), v(y), c(z) {};
    bool operator <(const Edge&that) {
        return c < that.c;
    }
}E;

void init(int n) {
    for (int i = 1; i <= n; i++)fa[i] = i;
}

int findr(int x) {
    if (fa[x] == x)return x;
    else return fa[x] = findr(fa[x]);
}

void merge(int x, int y) {
    int xr = findr(x);
    int yr = findr(y);
    if (xr != yr)fa[xr] = yr;
}

int main() {
    int n, m, u, v, c, ans = 0, cnt = 0;
    vector<E>edges;
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> c;
        edges.push_back(E(u, v, c));
    }
    sort(edges.begin(), edges.end());
    for (auto i : edges) {
        u = i.u, v = i.v;
        if (findr(u) != findr(v)) {
            merge(u, v);
            ans = max(ans, i.c);
            cnt++;
        }
    }
    cout << cnt << " " << ans << endl;
    return 0;
}