Submission

Score: 100

User: Hxluk.ka

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-09 11:47:28

#include <iostream>
#include <tuple>
#include <algorithm>
#include <vector>
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
const int nx=103, mx=1e4+3;
int n, m, u, v, w, cnt1, cnt2=2e9, par[nx];
vector<tuple<ll, int, int>> edgs, mst;
int fb(int x) {
    if (par[x]==x) return x;
    par[x]=fb(par[x]);
    return par[x];
}
int main() {
    cin.tie(0)->sync_with_stdio(0), cout.tie(0);

    cin>>n>>m;
    for (int i=0; i<m; i++) cin>>u>>v>>w, edgs.pb({w, u, v});
    for (int i=1; i<=n; i++) par[i]=i;

    sort(all(edgs));
    for (auto [w, u, v]:edgs) {
        int pu=fb(u), pv=fb(v);
        if (pu==pv) continue;
        par[pu]=pv;
        cnt1+=w;
        mst.pb({w, u, v});
    }

    for (int i=0; i<mst.size(); i++) {
        for (int j=1; j<=n; j++) par[j]=j;
        int cost=0, cnt=0;
        for (int j=0; j<m; j++) {
            if (mst[i]==edgs[j]) continue;
            auto [w, u, v]=edgs[j];
            int pu=fb(u), pv=fb(v);
            if (pu==pv) continue;
            par[pu]=pv;
            cost+=w;
            cnt++;
        }
        if (cnt==n-1) cnt2=min(cnt2, cost);
    }

    cout<<cnt1<<' '<<cnt2;

}