图结构练习——最小生成树

PRoblem Description

Input

Output

Example Input

3 21 2 11 3 11 0
Example Output
20
#include<stdio.h>#include<string.h>#define maxn 10005struct node{    int u;    int v;    int w;}tu[maxn];void getmap(int m){    int i;    for(i=1;i<=m;i++)    {        scanf("%d%d%d",&tu[i].u,&tu[i].v,&tu[i].w);    }}void QQsort(int left,int right){    int i,j,mid;    struct node m;    i=left; j=right; mid=tu[i].w; m=tu[i];    if(i>=j)        return ;    while(i<j)    {        while(i<j&&tu[j].w>=mid)            j--;        tu[i]=tu[j];        while(i<j&&tu[i].w<=mid)            i++;        tu[j]=tu[i];    }    tu[i]=m;    qqsort(left,i-1);    qqsort(j+1,right);}int find (int father[],int e){    int f;    f=e;    while(father[f]>0)    {        f=father[f];    }    return f;}void kruskal(int m){    int father[maxn];    int i,u,v,sum=0;    for(i=1;i<=m;i++)    {        father[i]=0;    }    for(i=1;i<=m;i++)    {        u=find(father,tu[i].u);        v=find(father,tu[i].v);        if(u!=v)        {            father[u]=v;            sum+=tu[i].w;        }    }    printf("%d/n",sum);}int main(){    int n,m,u,v,w;    while(scanf("%d%d",&n,&m)!=EOF)    {        getmap(m);        qqsort(1,m);        kruskal(m);    }    return 0;}