Submission

[PPPPPP-SSS]

Score: 0

User: MiyaZaki1072

Problemset: รัฐบาล

Language: cpp

Time: 0.055 second

Submitted On: 2025-04-28 19:09:45

#pragma GCC optimization ("03")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int p[200],n,m;
struct A{
    int u,v,w;
    bool operator<(const A&o)const{
        return w<o.w;
    }
}e[10100];


int fr(int u){
    if(p[u]==u)return u;
    return p[u] = fr(p[u]);
}
int MST(int dont){
    for(int i=1;i<=n;i++)p[i]=i;
    int ret=0,cnt=0;
    for(int i=1;i<=m;i++){
        if(i==dont)continue;
        int ru = fr(e[i].u),rv = fr(e[i].v);
        if(ru!=rv){
            p[ru]=rv;
            ret+=e[i].w;
            cnt++;
        }
    }
    if(cnt==n-1)return ret;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        e[i] ={u,v,w};
    }
    sort(e+1,e+m+1);
    int mst = MST(0);
    int ans=2e9;
    for(int i=1;i<=m;i++){
        int rn = MST(i);
        if(rn > mst)ans = min(ans,rn);
    }
    cout<<mst<<" "<<ans<<"\n";
}