社区讨论
大家看看我的代码有没有什么优化的地方
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 条回复,欢迎继续交流。
正在加载回复...