POJ 1233 并查集，最小生成树

题目链接：http://vjudge.net/problem/viewProblem.action?id=20289

题目意思：给你一些城市还有城市间的道路花费，让你找到一条花费最少的路，连通起所有的城市。

分析： 很经典的求最小生成树的问题。下面是kruskal算法的介绍

求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

#include<stdio.h>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define MAX 30005
int p[101],sum,num;    //p为并查集
struct edge       //图的结构体
{
    int sv,ev,w;//起始边，终边，权值。
};

struct edge e[10000];//必须开到大于(n*n-1)/2，否则必然RE。。。


bool cmp(const edge &a, const edge &b )
{
    if(a.w < b.w)
    return 1;
    return 0;
}

int find(int x){//并查集find函数
    if(x == p[x]) return x;
    else return find(p[x]);
 //   return p[x] == x ? x : (p[x] = find(p[x]));//压缩路径
}

void merge(int x,int y,int w){//并查集merge函数
    x = find(x); y = find(y);
    if(x != y){
        p[x] = y; sum += w; num++;
    }
}

int main(){
    int n,m,i;
    while(scanf("%d",&n)==1 && n != 0)
    {
        sum = 0; num = 1;
        m = n*(n-1)/2;
        for(i = 1;i <= n;i ++) p[i] = i;//初始化并查集

        for(i = 0;i < m;i ++){
            scanf("%d %d %d",&e[i].sv,&e[i].ev,&e[i].w);
        }

     
        sort(e,e+m,cmp);
        for(i = 0; i < m; i++)
        {
            merge(e[i].sv,e[i].ev,e[i].w);
            if(num == n) break;
        }
        printf("%d\n",sum);
    }
    return 0;
}