#include<bits/stdc++.h> using namespace std; const int N=110; struct Edge{ int a,b,w; }e[N*N]; int n; int k; // 表示一共有多少条边 int p[N]; // 并查集使用的集合数组 int ans; bool cmp(Edge e1,Edge e2){ return e1.w<e2.w; } // 查找元素的所在集合标识 int find(int x){ if(p[x]!=x) return p[x]=find(p[x]); return p[x]; } int kruskal(){ int cnt=0; // 对边进行排序 sort(e+1,e+k+1,cmp); // 初始化并查集 for(int i=1;i<=n;i++) p[i]=i; // 遍历每一条边 for(int i=1;i<=k;i++){ // 如果已经找到了n-1条边，就不要再继续遍历边集 if(cnt==n-1) break; int fa=find(e[i].a),fb=find(e[i].b); if(fa!=fb){ p[fb]=fa; ans+=e[i].w; cnt++; } } if(cnt<n-1) return -1; return ans; } int main(){ //freopen("P1546_2.in","r",stdin); //freopen("P1546_2_bak.out","w",stdout); cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int t; cin>>t; if(t!=0){ // 建边 k++,e[k]={i,j,t}; } } } cout<<kruskal()<<endl; return 0; }