Submission

Score: 0

User: someone

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-01-21 10:47:08

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;

vector<ll> dsu;

ll find(ll x) {
    if (dsu[x] == x) return x;
    else return dsu[x] = find(dsu[x]);
}

int main() {
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, pair<ll, ll>>> edges;
    vector<int> used;
    pair<ll, ll> ans = {0, 1e9};
    for (ll i = 0 ; i < m ; i++) {
        ll src, dest, w;
        cin >> src >> dest >> w;
        edges.push_back({w, {src, dest}});
    }
    sort(edges.begin(), edges.end());
    dsu.resize(n+1);
    // cout << dsu.size() << endl;
    for (ll i = 1 ; i <= n ; i++) dsu[i] = i;
    int cnt = 0;
    for (int i = 0 ; i < m ; i++) {
        ll w = edges[i].f;
        ll a = edges[i].s.f;
        ll b = edges[i].s.s;
        ll roota = find(a);
        ll rootb = find(b);
        if (roota != rootb) {
            ans.f += w;
            dsu[a] = rootb;
            used.push_back(i);
            cnt++;
        }
        if (cnt == n-1) break;
    }
    for (int i = 0 ; i < used.size() ; i++) {
        ll sum = 0;
        cnt = 0;
        for (int o = 1 ; o <= n ; o++) dsu[o] = o;
        for (int j = 0 ; j < m ; j++) {
            if (used[i] == j) continue;
            ll w = edges[j].f;
            ll a = edges[j].s.f;
            ll b = edges[j].s.s;
            ll roota = find(a);
            ll rootb = find(b);
            if (roota != rootb) {
                sum += w;
                dsu[a] = rootb;
                cnt++;
            }
            if (cnt == n-1) break;
        }
        if (sum <= ans.f) continue;
        ans.s = min(ans.s, sum);
    }
    cout << ans.f << ' ' << ans.s;
}