Submission

[-SSSSSSSSS]

Score: 0

User: NovemNotes

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2025-04-19 20:08:44

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

#define int long long
const int N = 1e2+2;
const int INF = 1e18;

struct stc{
	int u,v,w,i;
	bool operator<(const stc &x)const{
		return w<x.w;
	}
};
int n,m,ans,ans2=INF;
vector<stc> v;

int fr(int n,vector<int> &head){
	return (head[n]==n? n:head[n]=fr(head[n],head));
}

int kruskal(vector<int> head,int dont){
	int cnt=0;
	int edge=0;
	for(auto [a,b,w,i] : v){
		if(i==dont)continue;
		int ha=fr(a,head),hb=fr(b,head);
		if(head[ha]==hb)continue;
		head[ha]=hb;
		cnt+=w;
		edge++;
	}
	if(edge==n-1)return cnt;
	return INF;
}

int32_t main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m;
	vector<int> head(n+1);
	for(int i=1;i<=n;i++)head[i]=i;
	for(int i=0;i<m;i++){
		int a,b,c;cin >> a >> b >> c;
		v.push_back({a,b,c,i});
	}
	sort(v.begin(),v.end());
	ans = kruskal(head,-1);
	cout << ans << "\n";
	for(int i=0;i<m;i++){
		int tmp = kruskal(head,i);
		if(tmp>ans)ans2=min(ans2,tmp);
	}
	cout << ans2 << "\n";
	return 0;
}