Submission

Score: 0

User: SparkPun

Problemset: รัฐบาล

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-14 17:53:48

#include <bits/stdc++.h>
using namespace std;
const int N=110;
vector<tuple<int,int,int>>edge;
int parent[N],sz[N];
bool cmp(const tuple<int,int,int>&a,const tuple<int,int,int>&b){
    return get<2>(a)<get<2>(b);
}
int findSet(int u){
    if(parent[u]==u) return u;
    return parent[u]=findSet(parent[u]);
}
void unionSet(int u,int v){
    int U=findSet(u),V=findSet(v);
    if(U==V) return;
    if(sz[U]>=sz[V]){
        parent[V]=U;
        sz[U]+=sz[V];
    }
    else{
        parent[U]=V;
        sz[V]+=sz[U];
    }
}
int main(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        edge.push_back({u,v,w});
    }
    for(int i=1;i<=n;i++){
        parent[i]=i;
        sz[i]=1;
    }
    sort(edge.begin(),edge.end(),cmp);
    vector<int>used;
    int mst=0;
    for(int i=0;i<m;i++){
        auto [u,v,w]=edge[i];
        if(findSet(u)!=findSet(v)){
            unionSet(u,v);
            mst+=w;
            used.push_back(i);
        }
    }
    set<int>ans;
    ans.insert(mst);
    for(auto x:used){
        int sum=0,cnt=0;
        for(int j=1;j<=n;j++){
            parent[j]=j;
            sz[j]=1;
        }
        for(int j=0;j<m;j++){
            if(x==j) continue;
            auto [u,v,w]=edge[j];
            if(findSet(u)!=findSet(v)){
                unionSet(u,v);
                sum+=w;
                cnt++;
            }
        }
        if(cnt==n-1) ans.insert(sum);
    }
    int cnt=0;
    for(auto x:ans){
        if(cnt!=2){
            cout << x << " ";
            cnt++;
        }
    }
}