最小生成树
2025-12-21 11:33:10
发布于：广东
0阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int x,y,len;
};
node arr[10000];
int cnt=1;
int fa[110];
int get(int x){
if(fa[x]=x) return x;
return fa[x]=get(f[x]);
}
void merge(int x,int y){
fa[get(x)]=get(y);
}
bool cmp(node a,node b){
return a.len<b.len;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int len;cin>>len;
if(i<j){
arr[cnt].x=i;
arr[cnt].y=j;
arr[cnt].len=len;
cnt++;
}
}
}
sort(arr+1,arr+cnt,cmp);
int sum=0,ans=0;
for(int i=1;i<cnt;i++){
int x=arr[i].x,y=arr[i].y;
if(get(x)!=get(y)){
merge(x,y);
sum+=arr[i].len;
ans++;
}
}
if(ans==n-1) cout<<sum;
else cout<<"无法构成生成树";
return 0;
}
这里空空如也
有帮助，赞一个