全re求调
查看原帖
全re求调
632459
Vamppit楼主2024/1/20 10:57
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000000,inf=2147483647;
int cnt,tot,ans,n,m,head[maxn],fa[maxn],k;
bool qwq;
struct edge{
	int w=inf,to,next;
}e[maxn*4];
bool cmp(edge a, edge b){return a.w<b.w;}
int fid(int u)
{
	if(u==fa[u]) return fa[u];
	return fa[u]=fid(fa[u]);
}
int lin(int u,int v)
{
	fa[fid(u)]=fid(v);
}
int main()
{
	int x;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].to>>e[i].next>>x;
		if(x<e[i].w) e[i].w=x;
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+m+1,cmp);
	k=0; ans=0;
	for(int i=1;i<=m;i++)
	{
		if(fid(e[i].next)!=fid(e[i].to))
		{
			lin(e[i].next,e[i].to);
			k++;ans=e[i].w;
		}
		if(k==n-1) break ;
	}
	cout<<n-1<<" "<<ans;
	return 0;
}
2024/1/20 10:57
加载中...