rt。第二个样例点就过不去,输出为4。可能是我现在脑子比较糊,或者实力还不够,有哪位大佬能帮我看一下吗?
#include <bits/stdc++.h>
using namespace std;
struct s {
int u;
int v;
int w;
} a[5005];
int fa[10001];
int sum,ans,cnt;
bool cmp(s x,s y) {
return x.w<y.w;
}
void build(int x,int y,int z){
sum++;
a[sum].u=x;
a[sum].v=y;
a[sum].w=z;
}
int find(int x) {
if(fa[x]!=x) {
fa[x]=find(fa[x]);
}
return fa[x];
}
void unionn(int x,int y) {
int pa=find(x);
int pb=find(y);
if(pa!=pb) {
fa[pa]=pb;
}
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1; i<=m; i++) {
for(int j=1; j<=m; j++) {
int x;
cin>>x;
if(x!=0&&i<j) {
build(i,j,x);
}
}
}
for(int i=1;i<=m;i++){
fa[i]=i;
build(0,i,n);
}
sort(a+1,a+sum+1,cmp);
for(int i=1;i<=sum;i++){
if(find(a[i].u)!=find(a[i].v)){
ans+=a[i].w;
unionn(a[i].u,a[i].v);
cnt++;
}
if(cnt==m-1){
break;
}
}
cout<<ans;
return 0;
}