Submission

Score: 100

User: s0m30n3

Problemset: รัฐบาล

Language: cpp

Time: 0.005 second

Submitted On: 2026-02-03 19:26:09

#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
using namespace std;

vector<int> parent;

struct Edge{
    int u,v,w;
};

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

bool unite(int a, int b){
    a = find(a);
    b = find(b);
    if(a==b) return false;
    parent[b] = a;
    return true;
}

int main(){
   int n,m;
   cin >> n >> m;
   parent.resize(n+5, -1);
   vector<Edge> edges(m);
   for(int i=0;i<m;i++){
      cin >> edges[i].u >> edges[i].v >> edges[i].w;
   }
   sort(edges.begin(), edges.end(), [](Edge &a, Edge &b){
     return a.w < b.w;
   });
   for(int i=1;i<=n;i++) parent[i]=i;
   int mst_cost=0;
   vector<int> used = {};
   for(int i=0;i<m;i++){
     if(unite(edges[i].u, edges[i].v)){
        mst_cost+=edges[i].w;
        used.push_back(i);
     }
   }

   int second_mst = INT_MAX;
   for(int skip : used){
    for(int i=1;i<=n;i++) parent[i] = i;
    int cost=0;
    int cnt=0;
    for(int i=0;i<m;i++){
        if(i == skip) continue;
        if(unite(edges[i].u , edges[i].v)){
          cost+=edges[i].w;
          cnt++;
        }
    }
    if(cnt == n-1){
        second_mst = min(second_mst,cost);
    }
   }
   cout << mst_cost << " " << second_mst;
}