Submission

Score: 100

User: mydKN

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-10 18:15:13

#include <bits/stdc++.h>

using namespace std;

#define tiii tuple<int, int, int>
#define emb emplace_back

const int maxn = 110;
const int inf = 2e9;

int n, m;
vector<tiii> edge;
int pa[maxn];
int res, ex = inf;
vector<int> ban;

int findset(int u){
	if(pa[u] == u) return u;
	return pa[u] = findset(pa[u]);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=0;i<m;++i){
		int u, v, w;
		cin >> u >> v >> w;
		edge.emb(w, u, v);
	}
	sort(edge.begin(), edge.end());
	iota(pa, pa+n+1, 0);
	for(int i=0;i<m;++i){
		auto [w, u, v] = edge[i];
		int pu = findset(u), pv = findset(v);
		if(pu != pv){
			pa[pv] = pu;
			res += w;
			ban.emb(i);
		}
	}
	for(auto e : ban){
		int sum = 0, cnt = 0;
		iota(pa, pa+n+1, 0);
		for(int i=0;i<m;++i){
			if(e == i) continue;
			auto [w, u, v] = edge[i];
			int pu = findset(u), pv = findset(v);
			if(pu != pv){
				pa[pv] = pu;
				sum += w;
				++cnt;
			}
		}
		if(cnt == n-1) ex = min(ex, sum);
	}
	cout << res << " " << ex;
}