记录编号	513464	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.792 s
提交时间	2018-10-11 13:45:27	内存使用	33.69 MiB

#include<bits/stdc++.h>
using namespace std;
struct node
{ int x;
  int y;
  int z;
}d[2250001];
int f[2000001];
int m,n,cnt,ans,tot;
int find(int x)
{ if (f[x]!=x) f[x]=find(f[x]);
  return f[x];
}
int cmp(node a,node b)
{ return a.z<b.z;
}
int main()
{ freopen("mcst.in","r",stdin);
  freopen("mcst.out","w",stdout);
  scanf("%d",&n);
  for (int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
  { int x;
    scanf("%d",&x);
    if (x!=-1) {tot++;d[tot].x=i;d[tot].y=j;d[tot].z=x;}}
  sort(d+1,d+tot+1,cmp);
  for (int i=1;i<=n;i++)
  f[i]=i;
  for (int i=1;i<=tot;i++)
  { int u=find(d[i].x),v=find(d[i].y);
    if (u==v) continue;
    cnt++;
    ans+=d[i].z;
    f[u]=v;
    if (cnt==n-1) break;
    if (i==10000) {printf("-1");return 0;}
  }
  printf("%d",ans);
  return 0;
}