首页 > 代码库 > 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 (最小生成树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。