这道题其实跟 Lougu P2502 & SSL1312 A-B 数对【并查集】 蛮像的
相对来说其实这题更简单。
先排序，
再逐个判断当前边的左端点和右端点是否在一个集合内，
不在就合并，同时累加边权，
最后直接输出累加结果即可。
具体：
看代码
//无注释
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,x,m,js,ans,fa[100010];
struct node
{int x,y,v;
}a[100010];
bool cmp(const node&a,const node&b)
{return a.v<b.v;
}
int find(int x)
{if(fa[x]==x)return fa[x];return fa[x]=find(fa[x]);
}
int main()
{cin>>n;for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){cin>>x;if(x!=0){m++;a[m].x=i,a[m].y=j,a[m].v=x;}}for(int i=1; i<=n; i++)fa[i]=i;sort(a+1,a+1+m,cmp);for(int i=1; i<=m; i++){if(find(a[i].x)!=find(a[i].y)){fa[find(a[i].x)]=find(a[i].y);ans+=a[i].v;js++;}if(js==n-1)break;}cout<<ans;return 0;
}