Submission

[PPPPPP-SSS]

Score: 0

User: MiyaZaki1072

Problemset: รัฐบาล

Language: cpp

Time: 0.003 second

Submitted On: 2025-04-28 19:19:53

#pragma GCC optimization ("03")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
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]);
}
vector<int>use;
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(dont==0)use.push_back(i);
        }
    }
    if(cnt==n-1)return ret;
    else return 1e9;
}
signed 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(auto &x:use){
        int rn = MST(x);
        if(rn > mst)ans = min(ans,rn);
    }
    cout<<mst<<" "<<ans<<"\n";
}