Submission

Score: 0

User: Test

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-20 21:15:43

#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);
    sz.assign(n,1);
    for(int i=1;i<=n;i++) pa[i]=i;

    int cost = 0;
    int cnt = 0;
    vector<int> used; // ?? index ?ͧ edge ???????? MST
    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;
        }
    }
    int st_mst = cost;
    int nd_mst = 1e9;
    for(int banned : used){

        pa.resize(n);
        sz.assign(n,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;
}