Submission

[PPPPPPPPPP]

Score: 100

User: lufychop

Problemset: รัฐบาล

Language: cpp

Time: 0.005 second

Submitted On: 2025-04-19 20:27:20

#include <bits/stdc++.h>

using namespace std;

int root[101];

int findroot(int i)
{
	if(root[i]==i)
	{
		return i;
	}
	return root[i]=findroot(root[i]);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,u,v,w;
	cin>>n>>m;
	int ans1=0,ans2=1e9,tmp,cnt;
	vector<int> ans;
	vector<pair<int,pair<int,int>>> edge;
	for(int i=1;i<=n;i++)
	{
		root[i]=i;
	}
	for(int i=0;i<m;i++)
	{
		cin>>u>>v>>w;
		edge.push_back({w,{u,v}});
	}
	sort(edge.begin(),edge.end());
	for(int i=0;i<m;i++)
	{
		u=edge[i].second.first;
		v=edge[i].second.second;
		w=edge[i].first;
		u=findroot(u);
		v=findroot(v);
		if(u!=v)
		{
			ans1=ans1+w;
			root[u]=v;
			ans.push_back(i);
		}
	}
	for(int k=0;k<ans.size();k++)
	{
		tmp=0;
		cnt=0;
		for(int i=1;i<=n;i++)
		{
			root[i]=i;
		}
		for(int i=0;i<m;i++)
		{
			if(i==ans[k])
			{
				continue;
			}
			u=edge[i].second.first;
			v=edge[i].second.second;
			w=edge[i].first;
			u=findroot(u);
			v=findroot(v);
			if(u!=v)
			{
				tmp=tmp+w;
				cnt++;
				root[u]=v;
			}
		}
		if(cnt!=n-1)
		{
			continue;
		}
		ans2=min(ans2,tmp);
	}
	cout<<ans1<<" "<<ans2;
	return 0;
}
/*
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
*/