Submission

Score: 100

User: dddrrrr

Problemset: รัฐบาล

Language: cpp

Time: 0.008 second

Submitted On: 2026-03-12 22:12:38

#include <bits/stdc++.h>
#define int long long
const int MOD = 1e7 + 9;
using namespace std;

int n ,m;
struct DSU{
	vector <int> parent ,sz;
	DSU(int n){
		parent.resize(n);
		sz.resize(n ,0);
		for(int i=0 ;i<n ;i++)parent[i] = i;
	}
	
	int find(int x){
		if(x == parent[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;
		if(sz[a] < sz[b])swap(a ,b);
		sz[a] += sz[b];
		parent[b] = a;
		return true;
	}
};

vector <vector <int>> inmst;
int mst(vector <vector <int>> &edges){
	DSU dsu(n+1);
	int sum = 0 ,cnt = 0;
	for(int i=0 ;i<m ;i++){
		int w=edges[i][0] ,a=edges[i][1] ,b=edges[i][2];
		if(dsu.unite(a ,b)){
			cnt ++;		
			inmst.push_back(edges[i]);
			sum += w;
		}
	}
	
	if(cnt != n-1)return LLONG_MAX;	
	return sum;
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	
	vector <vector <int>> edges;
	for(int i=0 ;i<m ;i++){
		int u ,v ,w;
		cin >> u >> v >> w;
		edges.push_back({w ,u ,v});
	}
	
	sort(edges.begin() ,edges.end());
	int one = mst(edges);
	
	
	sort(inmst.begin() ,inmst.end());
	int second = LLONG_MAX;
	for(int i=0 ;i<inmst.size() ;i++){
		int sum = 0 ,cnt = 0;
		DSU dsu(n+1);

		for(int j=0  ;j<m ;j++){
			if(edges[j] == inmst[i])continue;
			int w=edges[j][0] ,a=edges[j][1] ,b=edges[j][2];
			if(dsu.unite(a ,b)){		
				sum += w;
				cnt++;
			}
		}
		
		if(cnt != n-1)continue;
		second = min(second ,sum);
	}
	
	cout << one << ' '<< second;
	
	
	return 0;
}