Submission

Score: 100

User: august

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-15 20:33:49

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

int fnd(int u, vector<int> &par) {
    if (par[u] == u) return u;
    return par[u] = fnd(par[u], par);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>> n>> m;

    vector<pair<int, pair<int,int>>> g;
    for (int i=0; i<m; i++) {
        int u,v,w;
        cin>> u>> v>> w;

        g.push_back({w, {u,v}});
    }

    sort(g.begin(), g.end());
    int ans1=0, ans2=INT_MAX;
    vector<int> par(n+1);
    iota(par.begin(), par.end(), 0);
    

    vector<int> span;
    for (int i=0; i<m; i++) {
        int u=g[i].second.first, v=g[i].second.second, w=g[i].first;

        int a=fnd(u, par);
        int b=fnd(v, par);
        if (a!=b) {
            ans1+=w;
            span.push_back(i);
            par[a]=b;
        }
    }

    for (auto &id : span) {
        int tem=0, compo = n;
        vector<int> par2(n+1);
        iota(par2.begin(), par2.end(), 0);

        for (int i=0; i<m; i++) {
            if (i == id) continue;

            int u=g[i].second.first, v=g[i].second.second, w=g[i].first;

            int a=fnd(u, par2);
            int b=fnd(v, par2);
            if (a!=b) {
                tem+=w;
                compo--;
                par2[a]=b;
            }
        }
        //cout<< tem<< ' '<< g[id].first<< '\n';
        if (compo == 1) ans2 = min(ans2, tem);
    }
    cout<< ans1<< ' '<< ans2;
}