题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=38

最小生成树水题~

代码：

#include "stdio.h"  // 最小生成树 Kruskal

#include "string.h"

#include "stdlib.h"

#define N 505

#define INF 0x3fffffff

int set[N];

int find(int x){ return set[x]==x?x:find(set[x]); }

void Init(int n){ for(int i=1; i<=n; ++i) set[i]=i; }

struct node

{

    int x,y;

    int cost;

}p[N*N];

int cmp(const void *a,const void *b)

{

    node *c = (node *)a;

    node *d = (node *)b;

    return c->cost - d->cost;

}

int main()

{

    int T;

    int n,m;

    int i,k;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d %d",&n,&m);

        for(i=0; i<m; ++i)

            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].cost);

        qsort(p,m,sizeof(p[0]),cmp);

        int ans = INF;

        for(i=0; i<n; ++i)

        {

            scanf("%d",&k);

            ans = ans<k?ans:k;

        }

        Init(n);

        int fa,fb;

        for(i=0; i<m; ++i)

        {

            fa = find(p[i].x);

            fb = find(p[i].y);

            if(fa==fb) continue;

            ans += p[i].cost;

            if(fa>fb)

                set[fa] = fb;

            else

                set[fb] = fa;

        }

        printf("%d\n",ans);

    }

    return 0;

}