十 分 萌 新 求 助
查看原帖
十 分 萌 新 求 助
91956
Dreamweaver楼主2021/2/9 22:10
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge
{
	int s,t,c;
}ed[100010];
//bool cmp(edge a,edge b)
//{
//	return a.c>b.c;
//}
bool operator  < ( const edge &a,const edge &b)
{return a.c<b.c;}
int f[100010];
int get(int p)
{
	if(f[p]=p)	return p;
	return f[p]=get(f[p]);
}
int mm=0,cnt=0;
void kruskar()
{
	sort(ed+1,ed+m+1);
	for(register int i =1;i<=m;i++)
	{
		mm=ed[i].c;
		int a,b;
		a=ed[i].s;
		b=ed[i].t;
		a=get(a);
		b=get(b);
		if(a!=b)
		{
			cnt++;
		
			f[a]=b;
		}
		if(cnt==n-1)	
			return ;
	}
}
int main()
{
 	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)	
		f[i]=i; 
	for(int i=1;i<=m;i++)
	{
		
		int q,w,e;
		scanf("%d%d%d",&q,&w,&e);
		ed[i].s=q;
		ed[i].t=w;
		ed[i].c=e;
	}
	kruskar();
	cout<<n-1<<' '<<mm;
    return 0;
}

2021/2/9 22:10
加载中...