Submission

Score: 100

User: qwerty

Problemset: รัฐบาล

Language: cpp

Time: 0.006 second

Submitted On: 2025-09-19 23:14:18

// 84
# include <bits/stdc++.h>
using namespace std;

# define V vector<int>

int n, m;
V p;
vector<V> path;
V use;
int fp(int a) {
    if (p[a] == a) return a;
    return p[a] = fp(p[a]);
}

int mst(int curr) {
    int c = 0;
    int sum = 0;
    p.resize(n+1);
    iota(p.begin(), p.end(), 0);
    for (int i = 0 ; i < m; i++) {
        if (curr == i) continue;
        int w = path[i][0];
        int u = path[i][1];
        int v = path[i][2];
        if (fp(u) != fp(v)) {
            c++;
            sum+=w;
            p[fp(u)] = fp(v);
            if (curr == -1) use.push_back(i);
        }
    }
    if (c!=n-1) return INT_MAX;
    return sum;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0 ; i < m ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        path.push_back({w, u, v});
    }
    sort(path.begin(), path.end());
    int ans = mst(-1);
    int ans2 = INT_MAX;
    for (auto i : use) {
        ans2 = min(ans2, mst(i));
    }
    cout << ans << ' ' << ans2;
}