首页 > 代码库 > Hdu 1301 Jungle Roads (最小生成树)

Hdu 1301 Jungle Roads (最小生成树)

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1301

 

很明显,这是一道“赤裸裸”的最小生成树的问题;

我这里采用了Kruskal算法,当然用Prim算法也一样可以解题。

 

#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>using namespace std;typedef struct node{    int from, to;    int length;  //长度,指代问题中两地间的费用}node;const int maxn = 90;node edge[maxn];int pre[30];int N,turn;int cmp(const void *a, const void *b) // 比较函数{    return (*(node*)a).length-(*(node*)b).length;}inline int root( int i ) //用于判断是否两节点在同一树上{    while( pre[i] )        i=pre[i];    return i;}inline void input()  //输入{    char c1,c2;    int i,order;    int dis;    turn=0;    while(cin>>c1>>order)    {        for(i=0;i<order;i++)        {            cin>>c2>>dis;            edge[turn].from=c1-‘A‘;            edge[turn].to=c2-‘A‘;            edge[turn].length=dis;            turn++;        }        if( c1==‘A‘+N-2 ) //输入完成,退出            break;    }    return ;}inline int span(){    memset(pre,0,sizeof(pre));    qsort(edge,turn,sizeof(node),cmp); //根据长度排序    int cost=0;    int count=0;    int pos=-1;    int m,n;    while(count<N-1)    {        do{            pos++;            m=root( edge[pos].from );            n=root( edge[pos].to );        }while(n==m);                 //用于判断是否两节点在同一树上        cost = cost + edge[pos].length;        pre[m]=n;             //把该节点加入这棵树        count++;    }    return cost;}int main(){    while(cin>>N && N)    {        input();        int flag=span();        cout<<flag<<endl;    }    return 0;}

 

Hdu 1301 Jungle Roads (最小生成树)