Submission

[-SSSSSSSSS]

Score: 0

User: a0ms1n

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

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

#include <bits/stdc++.h>
using namespace std;
#define int long long 

int n,m;
vector<pair<int,pair<int,int>>> V;
vector<int> parent;

int find(int a){
    if(parent[a]==a)return a;
    return parent[a] = find(parent[a]);
}

vector<int> used_edge;

int MST(int x=-1){
    int cnt = 0;
    int sum = 0;
    iota(parent.begin(),parent.end(),0);
    for(int i=0;i<m && cnt<n-1;i++){
        if(x==i)continue;
        auto [w,p] = V[i];
        auto [u,v] = p;
        if(find(u) != find(v)){
            cnt++;
            sum += w;
            parent[find(u)] = find(v);
            used_edge.push_back(i);
        }
    }
    if(cnt!=n-1)return LLONG_MAX;
    return sum;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>n>>m;
    parent.resize(n+1);
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        V.push_back({w,{u,v}});
    }
    sort(V.begin(),V.end());
    int d1 = MST();
    int d2 = LLONG_MAX;
    for(int c:used_edge){
        //cout<<MST(c)<<'\n';
        d2 = min(d2,MST(c));
    }
    cout<<d1<<' '<<d2;


    return 0;
}