Submission

Score: 100

User: Neozaawwman1

Problemset: รัฐบาล

Language: cpp

Time: 0.030 second

Submitted On: 2026-03-14 10:46:12

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,M;
int pa[105];
struct Data{
    int u,v,id;
    ll w;
    bool operator<(const Data&d2) const{
        return w>d2.w;
    }
};
priority_queue<Data> pq;
vector<Data> ed;
vector<int> used;
int findpa(int a){
    if(pa[a]==a)return a;
    return pa[a]=findpa(pa[a]);
}
void reset(int n){
    for(int i=1; i<=n; i++){
        pa[i]=i;
    }
}
void clear(){
    while(!pq.empty()){
        pq.pop();
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>N>>M;
    reset(N);
    for(int i=0; i<M; i++){
        Data inp;cin>>inp.u>>inp.v>>inp.w;
        inp.id=i;
        pq.push(inp);
        ed.push_back(inp);
    }
    int n = N;
    ll ct=0;
    while(!pq.empty() && n>1){
        Data cur = pq.top();pq.pop();
        int u = cur.u;
        int v = cur.v;
        ll w =cur.w;
        int pau=findpa(u);
        int pav=findpa(v);
        if(pau==pav)continue;
        pa[pau]=pav;
        ct+=w;
        used.push_back(cur.id);
        n--;
    }
    cout<<ct<<' ';
    
    ll ans = LLONG_MAX;
    for(auto block:used){
        reset(N);
        n = N;
        clear();
        for(auto x:ed){
            pq.push(x);
        }
        ll ct=0;
        while(!pq.empty() && n>1){
            Data cur = pq.top();pq.pop();
            if(cur.id==block)continue;
            int u = cur.u;
            int v = cur.v;
            ll w =cur.w;
            int pau=findpa(u);
            int pav=findpa(v);
            if(pau==pav)continue;
            pa[pau]=pav;
            ct+=w;
            n--;
        }
        if(n==1){
            ans = min(ans,ct);
        }
    }
    cout<<ans;
    return 0;
}