记录编号	157335	评测结果	AAAAAAAAAA
题目名称	[USACO 3.1] 最短网络	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2015-04-08 16:51:15	内存使用	0.47 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge{
	int qs,zz,w;
}E[10000];
int f[10000],ans=0,k=0,n,m;

int find(int x) 
{ 
     return x==f[x]?x:f[x]=find(f[x]);  
}
  
void uinon(int x,int y)  
{  
    int p=find(x),q=find(y);  
    if(p!=q)  
    {  
        f[p]=q;   
    }  
} 

int cmp(const Edge &x,const Edge &y){
	return x.w<y.w;
} 

int main()
{
 freopen("agrinet.in","r",stdin);
 freopen("agrinet.out","w",stdout);
 cin>>n;
 for (int i=1;i<=n;++i)
  f[i]=i;
 for (int i=1;i<=n;++i)
  for (int j=1;j<=n;++j)
  {
  	int x;
  	cin>>x;
  	if (x!=0)
  	{
  		m++;
  		E[m].qs=i;
  		E[m].zz=j;
  		E[m].w=x;
  	}
  } 
 sort(E+1,E+m+1,cmp);
 for (int i=1;i<=m;++i)
 {
 	if (find(E[i].qs)!=find(E[i].zz))
 	{
 		uinon(E[i].qs,E[i].zz);
 		ans+=E[i].w;
 		k++;
 	}
 	if (k==n-1) 
 	{
 		cout<<ans;
 		return 0;
 	}
 }
}