#include<bits/stdc++.h> using namespace std; int f[10001],r[10001];//保存父节点，和树的高度的数组 int n,ans; int k,m; int p=1; int find(int x) { if(x==f[x]) return x;//根节点为x else return f[x]=find(f[x]);//找父节点同时路径压缩 } bool same(int x,int y) { return find(x)==find(y); }//判别两个值是否在一个树 void unite(int x,int y) { x=find(x); y=find(y); if(x==y) return ;//判断两树是否构成环 if(r[x]<r[y]) { f[x]=y; } else { f[y]=x; if(r[x]==r[y]) r[x]++; }//合并 }//并查集模板代码 struct s { int x,y,w; }a[10005];//建立保存两村关系的结构体 bool cmp(s x,s y) { return x.w<y.w;//升序排列 } int main() { cin>>n; for(int i=1;i<=n;i++) { f[i]=i,r[i]=0;//初始化 for(int j=1;j<=n;j++) { cin>>k; if(j>i)//以中间的一排0为分界线，只有一半信息有用 { a[++m].x=i; a[m].y=j; a[m].w=k;//保存数据 }//经过找规律，发现有用的信息输入时，j总是大于i } } sort(a+1,a+m+1,cmp);//排序 for(int i=0;i<m;i++) { if(!same(a[i].x,a[i].y))//如果两数不会构成环 { ans+=a[i].w;//加上修建费用 unite(a[i].x,a[i].y);//合并两农场 p++;//增加相连农场数量 if(p==n) break;//如果每个农场都相连，跳出 } } cout<<ans<<endl;//输出数据 return 0; } /* 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 */