Submission

[PPPPPP-SSS]

Score: 0

User: hmmm

Problemset: รัฐบาล

Language: cpp

Time: 0.113 second

Submitted On: 2025-04-19 20:05:13

#include<bits/stdc++.h>
using namespace std;
using pii=array<int,3>;
const int N=105;
int pa[N],n,m;
vector<pii> p;

inline int find(int v){
    if(v==pa[v]) return v;
    return pa[v]=find(pa[v]);
}

inline void U(int a,int b){
    a=find(a);
    b=find(b);
    if(a!=b) pa[a]=b;
}

void chk(){
    for(int i=1;i<=n;i++) pa[i]=i;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    chk();
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        p.push_back({w,u,v});
    }
    sort(p.begin(),p.end());
    int ans1=0,ans2=1e9;
    for(auto e:p){
        auto w=e[0];
        auto u=e[1];
        auto v=e[2];
        if(find(u)!=find(v)){
            U(u,v);
            ans1+=w;
        }
    }
    for(int i=1;i<=m;i++){
        int cnt=1,sum=0;
        chk();
        for(int j=1;j<=m;j++){
            if(i==j) continue;
            auto w=p[j-1][0];
            auto u=p[j-1][1];
            auto v=p[j-1][2];
            if(find(u)!=find(v)){
                U(u,v);
                sum+=w;
                cnt++;
            }
        }   
        if(cnt==n && sum!=ans1) ans2=min(ans2,sum);
    }
    cout << ans1 << ' ' << ans2;
}