Submission

Score: 100

User: navysrimuang

Problemset: รัฐบาล

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-19 09:56:39

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;
using tiii = tuple<int,int,int>;
using pii = pair<int,int>;

int n,m;
int cmp = 0;
int sum1 = 0;
int used[102][102];
vector<tiii> ed;
vector<vector<pii>> adj;

int dfs(int u,int t,int p,int mx){
	if(u == t) return mx;
	for(auto [w,v] : adj[u]){
		if(v == p) continue;
		int rs = dfs(v,t,u,max(w,mx));
		if(rs != -1) return rs;
	}
	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 >> n >> m;
	adj.resize(n);
	for(int i = 0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		a--;b--;
		ed.pb({c,a,b});
	}

	sort(ed.begin(),ed.end());
	DSU dsu(n);	
	for(auto [w,a,b] : ed){
		if(dsu.unite(a,b)){
			used[a][b] = used[b][a] = 1;
			adj[a].pb({w,b});
			adj[b].pb({w,a});
			sum1 += w;
			cmp++;	
		}	

		if(cmp == n-1) break;
	}
	int bst = INT_MAX;
	for(auto [w,a,b] : ed){
		if(used[a][b]) continue;
		int mx = dfs(a,b,-1,0);
		int ty = sum1 - mx + w;
		if(ty < bst){
			bst = ty;
		}	
	}
		
	cout << sum1 << " " << bst << "\n";
	return 0;
}