社区讨论

震惊!O2优化的神奇!还是70分(代码风格简洁)求教大佬!

P3366【模板】最小生成树参与者 6已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi6xy9em
此快照首次捕获于
2025/11/20 12:38
4 个月前
此快照最后确认于
2025/11/20 12:38
4 个月前
查看原帖

我的程序开O2,35MS,920KBO2,35MS,920KB7070分,22991010测试点RERE;

不开O2,148MS,128000KBO2,148MS,128000KB6060分,22测试点MTEMTE66991010测试点WAWA

求教大佬————————

CPP
#include<bits/stdc++.h>
using namespace std;
const int X = 20110;
struct node{
	int u,v,c;
}G[X];
int f[X];
int n,m;

bool cmp(node a,node b){
	return a.c < b.c;
}

int find_f(int x){
	return x == f[x]?x:f[x] = find_f(f[x]);
}

void join(int fx,int fy){
	f[fy] = f[fx];
}

void init(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		cin>>G[i].u>>G[i].v>>G[i].c;
	}
	sort(G + 1,G + 1 + m,cmp);
	for(int i = 0;i <= n;i++){
		f[i] = i;
	}
}

int main(){
	int ans = 0,i = 1;
	init();
	for(int j = 1;i <= n - 1&&j <= m;){
		int fx = find_f(G[j].u),
			fy = find_f(G[j].v);
		if(fx == fy){
			j++;
		}
		else{
			i++;
			join(fx,fy);
			ans += G[j].c;
		}
	}
	if(i == n + 1){
		cout<<"orz"<<endl;
	}
	else{
		cout<<ans<<endl;
	}
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...