Submission

Score: 100

User: ki

Problemset: รัฐบาล

Language: cpp

Time: 0.009 second

Submitted On: 2026-03-20 22:15:30

#include<iostream>
#include<vector>
#include<functional>
#include<numeric>
using namespace std;
using tp=tuple<int,int,int>;
int n,m;
int main(){
	cin>>n>>m;
	vector<tp>v(m);
	for(auto&[z,x,y]:v){
		cin>>x>>y>>z;
		x--;y--;
	}
	sort(v.begin(),v.end());
	vector<int>p(n);
	iota(p.begin(),p.end(),0);
	function<int(int)>fset=[&](int x){
		return (p[x]==x?x:p[x]=fset(p[x]));
	};
	auto mg=[&](int x,int y){
		if((x=fset(x))==(y=fset(y)))return;
		p[y]=x;
	};
	int ans=0,ans2=1e9;
	vector<int>s;
	for(int i=0;i<m;i++){
		auto[z,x,y]=v[i];
		if(fset(x)==fset(y))continue;
		mg(x,y);
		s.emplace_back(i);
		ans+=z;
	}
	for(int i=0;i<s.size();i++){
		iota(p.begin(),p.end(),0);
		int xx=0,cc=0;
		for(int j=0;j<m;j++){
			auto[z,x,y]=v[j];
			if(fset(x)==fset(y))continue;
			if(j==s[i])continue;
			mg(x,y);
			xx+=z;
			cc++;
		}
		if(cc==n-1)ans2=min(ans2,xx);
	}
	cout<<ans<<' '<<ans2<<'\n';
}