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

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

Time Limit: 1000MS MemoryLimit: 65536KB

SubmitStatistic

PRoblemDescription

 有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

Input

 输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个正整数a b c，代表城市a和城市b之间可以修建一条公路，代价为c。

Output

 每组输出占一行，仅输出最小花费。

ExampleInput

3 2

1 2 1

1 3 1

1 0

ExampleOutput

2

0

Hint

Author

 赵利强'

#include <iostream>#include<bits/stdc++.h>using namespace std;int f[102000]={0},n,m,k,sum,book[102000];struct node{int u,v,w;}e[10002];void quicksort(int l,int r){    int i,j;    node t;    if(l>r)    return;    i = l;    j = r;    while(i!=j)    {        while(e[j].w>=e[l].w&&i<j)        {        j--;        }        while(e[i].w<=e[l].w&&i<j)        {        i++;        }        if(i<j)        {        swap(e[j],e[i]);        }    }    swap(e[l],e[i]);    quicksort(l,i-1);    quicksort(i+1,r);    return ;}int getf(int v){    if(f[v]==v)    {        return v;    }    else    {        f[v] = getf(f[v]);        return f[v];    }}int amerge(int l,int r){    int t1,t2;    t1 = getf(l);    t2 = getf(r);    if(t1!=t2)    {        f[t2] = t1;        return 1;    }    return 0;}int main(){    int x,y,i;    while(~scanf("%d%d",&n,&m))    {        if(n==0)        {         printf("0/n");        continue;        }        sum =0;        //int nmax=0;//为图中出现的最大顶点编号        for(i=1;i<=n;i++)        {            f[i] = i;        }        int count=0;       // memset(book,0,sizeof(book));        for(i=1;i<=m;i++)        {            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);        }quicksort(1,m);       for(i=1;i<=m;i++)       {        if(amerge(e[i].u,e[i].v))        {            count++;            sum+=e[i].w;        }        if(count==n-1)        break;       }       printf("%d/n",sum);    }    return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 16msTake Memory: 252KBSubmit time: 2017-02-17 14:48:38****************************************************/