a[]的范围开大tle,开小re???
查看原帖
a[]的范围开大tle,开小re???
707488
ljx979楼主2024/10/17 12:06
include<bits/stdc++.h>
using namespace std;
int a[200005];
int ans=0;
int find(int a[],int i)
{
	while(i!=a[i])
		i=a[i];
	return i;
}
void ad(int a[],int x,int y)
{
	int r1=find(a,x);
	int r2=find(a,y);
	a[r2]=r1;
	return;
}
bool check(int a[],int x,int y)
{
	int r1=find(a,x);
	int r2=find(a,y);
	if(r1!=r2)
		return true;
	return false;
}
struct node
{
	int x,y,dis;
}e[100005];
bool cmp(const node a,const node b)
{
	return a.dis<b.dis;
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<=n;i++) a[i]=i;
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		e[i].x=x;
		e[i].y=y;
		e[i].dis=z;
	}
	sort(e,e+m,cmp);
	for(int i=0;i<m;i++)
	{
		int x=e[i].x;
		int y=e[i].y;
		if(check(a,x,y))
		{
//			cout<<x<<' '<<y<<' '<<e[i].dis<<endl;
			ans+=e[i].dis;
			ad(a,x,y);
		}
	}
	cout<<ans;
	return 0;
} 
2024/10/17 12:06
加载中...