HDU 1102 Contstructing Roads(最小生成ツリー＋Kruskalアルゴリズム入門)

【タイトルリンク】:click here~~
【題目の大意】:いくつかの道路がすでに修理済みであることを知っています.全部の道を通るには最小の費用が必要です.
【問題解決の考え方】:基礎のKruskyalアルゴリズムです.辺の権利値によって小さい時から大きい順に並べ替えて、条件に合って、生成樹に加入します.
コード:

/*
Author:HRW
kruskal+   
*/
#include <bits/stdc++.h>
using namespace std;
const int max_v=105;
const int inf=0x3f3f3f3f;
int u,v,n,m,a,b;
int father[max_v];
int find(int x){
    if(x==father[x]) return x;
    return father[x]=find(father[x]);
}
struct Edge{
    int u,v,w;
} edge[max_v*max_v];
bool cmp(Edge a,Edge b){
    return a.w<=b.w;
}
int kruskal(int n,int m){
    sort(edge,edge+m,cmp);//            
    int x,y;
    int res=0;
    for(int i=0; i<m; i++){
        x=edge[i].u;
        y=edge[i].v;
        x=find(x);//            
        y=find(y);
        if(x!=y)
        {
            father[y]=x;
            res+=edge[i].w;
        }
    }
    return res;
}
void init(){
    for(int i=1; i<=n; i++)
        father[i]=i;
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        int aa;
        int p=0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++){
                scanf("%d",&aa);
                if(i>=j) continue;//!  
                edge[p].u=i;
                edge[p].v=j;
                edge[p].w=aa;
                p++;
            }
        init();
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&a,&b);
            a=find(a);
            b=find(b);
            father[b]=a;
        }
        printf("%d
",kruskal(n,p));
    }
    return 0;
}