TLE完全不知道为什么
查看原帖
TLE完全不知道为什么
307826
Lamorak楼主2021/1/26 12:00
#include<bits/stdc++.h>
using namespace std;
const int M=7*1e5;
struct node{
	int u,v,w;
}a[M];
int n,m,k,pre[M],ans,sum;
bool cmp(node d1,node d2){
	d1.w<d2.w;
}
int find(int x){
	int step,now=x,root=x;
	while(root!=pre[root]) root=pre[root];
	while(now!=root){
		step=pre[now];
		pre[now]=root;
		now=step;
	}
	return root;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) pre[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++){
		int rx=find(a[i].u);
		int ry=find(a[i].v);
		if(rx!=ry){
			sum++;
			ans+=a[i].w;
			pre[rx]=ry;
		}
		if(sum>=n-k){
			printf("%d",ans);
			return 0;
		}
	}
	printf("No Answer");
	return 0;
}
2021/1/26 12:00
加载中...