求助,三个RE(开O2变TLE),数组开的应该是对的
查看原帖
求助,三个RE(开O2变TLE),数组开的应该是对的
813765
PC114514楼主2023/7/15 11:04

RT

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
	int x,y,z;
	friend int operator < (node a,node b){
		return a.z <= b.z;
	}
};
int n,m,fa[5005],x,y,z,cnt=0,sum=0;
node a[400005];
int find(int x){
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		fa[i] = i;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		a[i].x = x;
		a[i].y = y;
		a[i].z = z;
	}
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++){
		if(find(a[i].x)!=find(a[i].y)){
			fa[find(a[i].y)] = find(a[i].x);
			sum += a[i].z;
			cnt++;
			if(cnt==n-1)
				break;
		}
	}
	if(cnt!=n-1)
		cout<<"orz";
	else
		cout<<sum;
	return 0;
}
2023/7/15 11:04
加载中...