Submission

Score: 100

User: VggT

Problemset: รัฐบาล

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-13 19:16:36

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

vector<int> parent;

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

bool unite(int x, int y)
{
	int BossX = find(x);
	int BossY = find(y);
	if(BossX != BossY)
	{
		parent[BossY] = BossX;
		return true;
	}
	return false;
}

void mst(vector<vector<int>> &graph, int n)
{
	sort(graph.begin(),graph.end());
	vector<int> usedindex;
	int ans1 = 0;
	int ans2 = INT_MAX;
	int temp = n;
	
	
	for(int i = 0; i < n; i+=1) parent[i] = i;
	
	for(int i = 0; i < graph.size(); i+=1)
	{
		if(temp-1 <= 0) break;
		int u = graph[i][1];
		int v = graph[i][2];
		int dist = graph[i][0];
		if(unite(u,v))
		{
			
			ans1+=dist;
			temp-=1;
			usedindex.push_back(i);
		}	
	}
	
	for(int i = 0; i < usedindex.size(); i+=1)
	{
		parent.assign(n,0);
		temp = n;
		int sum = 0;
		for(int k = 0; k < n; k+=1) parent[k] = k;
		for(int j = 0; j < graph.size(); j+=1)
		{
			if(j == usedindex[i]) continue;
			int u = graph[j][1];
			int v = graph[j][2];
			int dist = graph[j][0];
			if(unite(u,v))
			{
				
				sum+=dist;
				temp-=1;
			}
		}
		if(temp-1 == 0)
		{
			ans2=min(ans2,sum);
		}
		
	}
	
	cout << ans1 << ' ' << ans2;
}

int main()
{
	int n, m; cin >> n >> m;
	vector<vector<int>> graph;
	parent.resize(n,0);
	
	
	for(int i = 0; i < m; i+=1)
	{
		int u,v,dist;
		cin >> u >> v >> dist;
		u-=1; v-=1;
		graph.push_back({dist,u,v});
	}
	
	
	mst(graph,n);
	
	
	return 0;
}