http://poj.org/problem?id=1258
题意 ： john当上了镇长，打算给每个农场都连接网络，需要用最小的成本连接其他所有农场，所以要找最少的纤维连在一起，任何两个农场之间的距离不超过十万。输入n，下面有n行n列，代表着每两个农场的距离，对角线为0，因为自己到自己是为0；
解题思路 ： 这个题要包含所有的农场，赤果果的最小生成树，这个题的话，注意是多组输入还有数组不要开得太小，算法的话prim和kruskal都可以，我用的是prim。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ans,dis[][];
const int INF = << ;
int vis[],n,low[];
int prim()
{
memset(vis,,sizeof(vis));
int i,j,flag,min;
ans = ;
for(i = ; i <= n ; i++)
{
low[i] = dis[][i];
}
vis[] = ;
for(i = ; i <= n ; i++)
{
min = INF;
for(j = ;j <= n ; j++)
{
if(min > low[j]&&!vis[j])
{
min = low[j] ;
flag = j;
}
}
if(min >= INF)
{
flag = - ;
break ;
}
ans+=min ;
vis[flag] = ;
for(j = ; j <= n ; j++)
{
if(dis[flag][j] < low[j] && !vis[j])
low[j] = dis[flag][j];
}
}
return ans ;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= n ; j++)
{
cin>>dis[i][j] ;
}
}
ans = prim();
cout<<ans<<endl;
}
return ;
}