Submission

Score: 0

User: navysrimuang

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-18 23:59:45

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<ll,int>>> adj;
ll dfs(int u,int t, int p,ll mm){
	if(u == t) return mm;
	for(auto [w,v] : adj[u]){
		if(v == p) continue;	
		int r = dfs(v,t,u,max(w,mm));
		if(r != -1) return r;
	}
	return -1;
}
struct DSU{
	vector<int> par, sz;
	DSU(int n){
		par.resize(n); sz.resize(n,1);
		iota(par.begin(),par.end(),0);
	}
	int find(int x){
		if(par[x] == x) return x;
		else return (par[x] = find(par[x]));
	}
	bool unite(int a,int b){
		int ra = find(a);
		int rb = find(b);
		if(ra == rb) return 0;

		if(sz[ra] < sz[rb]) swap(ra,rb);
		par[rb] = ra;
		sz[ra] += sz[rb];
		return 1; 
	}
};
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n,m;
	vector<tuple<ll,int,int>> e;
	cin >> n >> m;
	DSU dsu(n);
	for(int i = 0;i<m;i++){
		int a,b; ll c;
		cin >> a >> b >> c;
		a--; b--;
		e.push_back({c,a,b});
	}
	sort(e.begin(),e.end());
	int cnt = 0; ll sum = 0;
	adj.resize(n);
	vector<vector<int>> used(n,vector<int>(n,0));
	for(auto [w,a,b] : e){
		if(dsu.unite(a,b)){
			used[a][b] = used[b][a] = 1;
			adj[a].push_back({w,b});
			adj[b].push_back({w,a});
			cnt++;
			sum += w;
		}
		if(cnt == n-1) break;
	}
	// get an min edge; try to add that -> remove max form that cycle coutn
	ll best = LLONG_MAX;
	for(auto [w,a,b] : e){
		if(used[a][b]) continue;
		ll mx = dfs(a,b,-1,0); 
		ll now = sum + w - mx;
		if(now > sum){
			best = min(best,now);
		}		
	}
	cout << sum << " " << best << "\n";
	return 0;
}