Submission

Score: 100

User: Test

Problemset: รัฐบาล

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-20 21:16:31

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

vector<int> pa, sz;

int find_root(int x){
    if(pa[x] == x) return x;
    return pa[x] = find_root(pa[x]);
}

bool un(int a,int b){
    a = find_root(a);
    b = find_root(b);
    if(a == b) return false;
    if(sz[a] < sz[b]) swap(a,b);
    pa[b] = a;
    sz[a] += sz[b];
    return true;
}

int main(){
    int n,e;
    cin >> n >> e;

    vector<tuple<int,int,int>> edge;
    for(int i=0;i<e;i++){
        int u,v,w;
        cin >> u >> v >> w;
        edge.push_back({w,u,v});
    }

    sort(edge.begin(), edge.end());

    pa.resize(n+1);
    sz.assign(n+1,1);
    for(int i=1;i<=n;i++) pa[i]=i;

    long long cost = 0;
    int cnt = 0;
    vector<int> used;

    for(int i=0;i<e;i++){
        int w = get<0>(edge[i]);
        int u = get<1>(edge[i]);
        int v = get<2>(edge[i]);

        if(un(u,v)){
            cost += w;
            cnt++;
            used.push_back(i);
            if(cnt == n-1) break;
        }
    }

    long long st_mst = cost;
    long long nd_mst = (long long)4e18;

    for(int banned : used){
        pa.resize(n+1);
        sz.assign(n+1,1);
        for(int i=1;i<=n;i++) pa[i]=i;

        cost = 0;
        cnt = 0;

        for(int i=0;i<e;i++){
            if(i == banned) continue;

            int w = get<0>(edge[i]);
            int u = get<1>(edge[i]);
            int v = get<2>(edge[i]);

            if(un(u,v)){
                cost += w;
                cnt++;
                if(cnt == n-1) break;
            }
        }

        if(cnt == n-1 && cost >= st_mst){
            nd_mst = min(nd_mst, cost);
        }
    }

    cout << st_mst << " " << nd_mst << "\n";
}