农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。 每两个农场间的距离不会超过100000

第一行： 农场的个数，N（3<=N<=100）。

第二行..结尾: 接下来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们每行限制在80个字符以内，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为线路从第i个农场到它本身的距离在本题中没有意义。

只有一个输出，是连接到每个农场的光纤的最小长度和。

4

0  4  9 21

4  0  8 17

9  8  0 16

21 17 16  0

28

思路：用结构体存边（如果边权为0可以跳过，也就是说（n.n）可以跳过，不存入边中 ），sort一下，使用并查集存不同的树，最后gg。

（类似贪心的思路）

Kruskal：

最开始把每个端点的根节点存为自己，然后不停的模拟建树（我也不知道这样的说法对不对，唔）。

每次寻找最小的边，判断这条边的起点的根节点是否与这条边的根节点相同。如果不相同，证明这两个点不在同一个树中。然后将一个根节点存为另一个根节点的父节点（即把两棵树存为一棵树）。（每次找到可以存的边，边树++）

最后，如果边数==端点个数-1，输出路径的长度，直接打断return 0

代码实现：

#include<stdio.h>
#include<algorithm>
using namespace std;
struct edge
{
int u;
int v;
int w;
}e[400000];
int flag,pre[1000],ans,n,cnt,t; 

//pre记录当前端点的父节点
int judge(int x)
{
int j;
j=x;
while(j!=pre[j])
{
j=pre[j];
}
int i;
i=x;
while(i!=j)
{
i=pre[i];
pre[i]=j;
}

//路径压缩
return j;
}

//找到当前边起点／终点的根节点
void find(int x)
{
int a,b;
a=judge(e[x].u);
b=judge(e[x].v);
if(a!=b)
{
pre[a]=b;
flag=1;
}
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int main()
{
int w;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
pre[i]=i;
for(int j=1;j<=n;j++)
{
scanf("%d",&w);
if(w!=0)
{
e[++cnt].u=i;
e[cnt].v=j;
e[cnt].w=w;
}
}
}
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;i++)
{
flag=0;
find(i);
if(flag==1)
{
ans=ans+e[i].w;
t++;
}
if(t==n-1)
{
printf("%d",ans);
return 0;
}
}
}

ps：小白第一次写博客，给位看官如果发现错误请帮忙纠正，求轻喷。