社区讨论

大家看看我的代码有没有什么优化的地方

P1546[USACO3.1] 最短网络 Agri-Net参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo27yl6x
此快照首次捕获于
2023/10/23 09:28
2 年前
此快照最后确认于
2023/11/03 09:43
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m;
int sum;
int longchang[101][101];
struct b{
    int a,b,bian;
};
int cont;
b B[200001];
int tree[200001];
bool cmp(b x,b y){
	return x.bian<y.bian;
}
int get(int x){
	if(tree[x]==x){
		return x;
	}
	return tree[x]=get(tree[x]);
}
int hebing(int x,int y){
	tree[get(x)]=get(y);
}
int main(){
	
	cin>>n;
	
	for(int i=1;i<=n;i++){
		tree[i]=i;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>longchang[i][j];
		}
	}
	int z=1;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(i!=j&&longchang[i][j]!=0){
				B[z].a=i;
				B[z].b=j;
				B[z].bian=longchang[i][j];
				z++;
			}
		}
	}
	
	sort(B+1,B+1+z,cmp);
	
	for(int i=1;i<=z;i++){
		if(get(B[i].a)!=get(B[i].b)){
			hebing(B[i].a,B[i].b);
			cont++;
			sum+=B[i].bian;
		}
		if(cont==n-1){
			cout<<sum;
			return 0;
		}
	}
}

回复

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

正在加载回复...