首页 > 代码库 > HDOJ 1301
HDOJ 1301
题目大意:
输入一个数n表示岛上的村庄数,接下来输入n-1行,每行先输入一个乡村名称,接下来输入与其邻接的乡村数,之后输入没给邻接的乡村及道路权值,以此类推共n-1行,最后题目要求输出该联通图的最小生成树的最小代价。
算法思想:
1.先建立一个邻接表,用来存储连通图。
2.从邻接表中读出,联通图的所有边。
3.将读出的边进行排序。
4.采用克鲁斯卡尔算法生成最小生成树。
5.输出最小代价。
代码如下:
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef struct node{//边节点 char adjvex;//邻接边 int value;//权值 node *next;//后继指针 }EdgeNode; typedef struct VertexNode{//表节点 char vertex; int num;//邻接边的数目 EdgeNode *firstedge; }VertexNode; typedef VertexNode Adjlist[30]; typedef struct { Adjlist adjlist; int n; }AlGraph; /*构造最小生成树*/ int node[30];//G->n节点数 typedef struct edge{ int value;//记录边的权值 char start,end;//记录边的两个端点 }Edge; Edge bian[80]; int cost;//记录最小代价 int num;//记录边的数目 int Count;//加入集合的边数 int Find_set(int n){//并查集 if(node[n]==-1) return n; return node[n]=Find_set(node[n]); } /*合并函数:将一条边的两个顶点加入到一个集合中*/ bool Merge(int s1,int s2){ int r1=Find_set(s1); int r2=Find_set(s2); if(r1==r2) return 0; if(r1<r2) node[r2]=r1; else node[r1]=r2; return 1; } bool cmp(Edge a,Edge b){ if(a.value<b.value) return true; return false; } int main(){ AlGraph *G=new AlGraph;//新建一个邻接表 while(cin>>G->n&&G->n!=0){//输入邻接表的顶点数 cost=0; num=0; Count=0; memset(node,-1,sizeof(node));//对节点初始化 for(int i=1;i<G->n;i++){ cin>>G->adjlist[i].vertex>>G->adjlist[i].num;//构件节点表 G->adjlist[i].firstedge=NULL;//节点表初始化 for(int j=1;j<=G->adjlist[i].num;j++){ EdgeNode *p=new EdgeNode; EdgeNode *q; if(j==1){ G->adjlist[i].firstedge=p; cin>>p->adjvex>>p->value; p->next=NULL; q=p;//记录当前节点 } else{ p->next=q->next;//先继承前驱节点的后继节点 q->next=p;//再连接前驱节点 cin>>p->adjvex>>p->value;//输入边节点的权值和节点 q=p;//记录当前节点 } } } //读取图中的每一条边 for(int i=1;i<G->n;i++){ EdgeNode *p=G->adjlist[i].firstedge; for(int j=1;j<=G->adjlist[i].num;j++) { bian[num].value=http://www.mamicode.com/p->value;>HDOJ 1301
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。