Submission

[PPPPPPPPPP]

Score: 100

User: NovemNotes

Problemset: รัฐบาล

Language: cpp

Time: 0.005 second

Submitted On: 2025-04-19 20:14:22

#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;
vector<int> use;

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(ha==hb)continue;
		head[ha]=hb;
		if(dont==-1)use.push_back(i);
		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 << " ";
	for(auto i:use){
		int tmp = kruskal(head,i);
		ans2=min(ans2,tmp);
	}
	cout << ans2 << "\n";
	return 0;
}