算法训练 安慰奶牛（最小生成树）

这道关于最小生成树的问题，起初让我百思不得解，所以就搁置了下来，今天才想着做做，一会儿我就跟你们说说我那可笑的理解、可笑的疑惑！
题目：
问题描述
Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。

输入格式
第1行包含两个整数N和P。
接下来N行，每行包含一个整数Ci。
接下来P行，每行包含三个整数Sj, Ej和Lj。

输出格式
输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。

样例输入
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6

样例输出
176

数据规模与约定
5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。

当我看到这个问题时，我首先被一句话搞懵了，“你每个晚上都会在同一个牧场(这是供你选择的)过夜”，这句话是在告诉我们什么？他要在这里住好几天？还是......最后我终于明白，考虑到最小生成树的问题的实现，这里肯定是在一天内完成交谈任务，并且回到初始的位置。那么我们就可以跟据题意知道，每条选择的路我们都要考虑到去与回，并且要考虑到谈话时间。然后我自己画了一个小的树，实际的去模拟了一下操作的过程，发现，除了起始位置外，其他各个结点（牧场）与牛的谈话次数均和边数相等，只有起始位置的多了一次，那么我们就好理解了，用起始位置多的这一次谈话时间（为了使时间最短，则需要选取最少的谈话时间的结点做起点）加上最小生成树的时间，即： min + Kruskal()。
代码如下：

#include <stdio.h>
#include <stdlib.h> //qsort()头文件

#define M 100002

typedef struct Edge     //边
{
    int S;      //牧场S
    int E;      //牧场E
    int L;      //通过时间L
} Edge;

Edge e[M];      //实例化边

int far[M];     //结点根指向
int C[M];       //和奶牛谈话时间
int sum = 0;
int N, P;       //N个结点，P条边

//qsort()需要调用的指针
int cmp(const void *a, const void *b)
{
    Edge *c = (Edge *)a;        //将指针void *a强制转换成(Edge *)a并赋给指针Edge *c
    Edge *d = (Edge *)b;        //将指针void *b强制转换成(Edge *)b并赋给指针Edge *d
    return c->L - d->L;         //由小到大排列
}

//寻找根结点，并将中间结点的标记都指向根结点
int find(int x)
{
    int i, k, r;
    r = x;
    //寻找根结点
    while (far[r] >= 0)
        r = far[r];
    k = x;
    //让由x结点一直到根结点中间所有的结点的下一个结点标记都指向根结点
    while (k != r)
    {
        i = far[k];
        far[k] = r;
        k = i;
    }
    //返回根结点
    return r;
}

//将两个结点联结
void Union(int S, int E)
{
    int rS, rE;
    int num;
    rS = find(S);
    rE = find(E);
    num = far[rS] + far[rE];        //必为负数
    //结点联结
    if(far[rS] < far[rE])
    {
        far[rE] = rS;
        far[rS] = num;
    }
    else
    {
        far[rS] = rE;
        far[rE] = num;
    }
}

//Kruskal算法，最小生成树
int Kruskal()
{
    int i;
    int S, E;
    int sumweight = 0, count = 0;
    for(i = 0; i < N; i++)      //初始化far
        far[i] = -1;
    qsort(e, P, sizeof(e[0]), cmp);     //对边的权进行由小到大排序
    for(i = 0; i < P; i++)
    {
        S = e[i].S;
        E = e[i].E;
        //如果S的根结点不等于E的根结点，说明没有生成回路，则选取这条边
        if(find(S) != find(E))
        {
            sumweight += e[i].L;
            Union(S, E);
            count++;        //边数
            if(count >= N - 1)
            {
                break;
            }
        }
    }
    return sumweight;
}

int main ()
{
    int i, min = M;
    int S, E, L;        //牧场S，牧场E，通过时间L

    scanf ("%d %d", &N, &P);

    for (i = 0; i < N; i++)
    {
        scanf ("%d", &C[i]);
        //选取睡觉的地方
        if (C[i] < min)
            min = C[i];
    }

    for (i = 0; i < P; i++)
    {
        scanf("%d %d %d",&S, &E, &L);
        //结点是从0开始存储，所以所有输入的结点需要减一存储
        e[i].S = S - 1;
        e[i].E = E - 1;
        //最小生成树，所以想要按要求安慰所有的奶牛，就必须考虑到来回
        e[i].L = L * 2 + C[S - 1] + C[E - 1];       //从一个结点到另一个结点再返回所用时间（包括谈话时间）
    }

    printf ("%d\n", min + Kruskal());       //在睡觉的牧场会多谈一次话
    return 0;
}

具体的原理以及思想都在代码中注释清楚了，希望有利于理解。
OVER！！！