管道铺设施工的最佳方案 完整程序代码.docx
- 文档编号:74897
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:7
- 大小:83.30KB
管道铺设施工的最佳方案 完整程序代码.docx
《管道铺设施工的最佳方案 完整程序代码.docx》由会员分享,可在线阅读,更多相关《管道铺设施工的最佳方案 完整程序代码.docx(7页珍藏版)》请在冰点文库上搜索。
管道过河工程施工方案
1)内容:
需要在某个城市n个居民小区之间铺设煤气管道,则在这n个居民小区之间只需要铺设n-1条管道即可。
假设任意两个小区之间都可以铺设管道,但由于地理环境不同,所需要的费用也不尽相同。
选择最优的方案能使总投资尽可能小,这个问题即为求无向网的最小生成树。
2)要求:
在可能假设的m条管道中,选取n-1条管道,使得既能连通n个小区,又能使总投资最小。
每条管道的费用以网中该边的权值形式给出,网的存储采用邻接表的结构。
3)测试数据:
使用下图给出的无线网数据作为程序的输入,求出最佳铺设方案。
右侧是给出的参考解。
4)输入输出:
参考
完整代码:
#include"iostream"
#include"stdlib.h"
#defineMAX_VERTEX_NUM20
typedeffloatWeightType;
typedefstructArcNode{
intadjvex;
WeightTypeweight;
structArcNode*nextarc;
}ArcNode;
typedefstructVertexNode{
chardata;
ArcNode*firstarc;
}VertexNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices;
intvexnum,arcnum;
intkind;
}ALGraph;
intLocateVex(ALGraphG,charv)
{
inti;
for(i=0;i { if(G.vertices[i].data==v) returni; } return-1; } voidCreateGraph(ALGraph&G) { inti,j,k; charvi,vj; WeightTypeweight; ArcNode*p,*q; std: : cout<<"请输入顶点个数,边数和图的类型: \n"; std: : cin>>G.vexnum>>G.arcnum>>G.kind; for(i=0;i { std: : cout<<"请输入各个顶点: \n"; std: : cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; } for(k=0;k { std: : cout<<"请输入两顶点和其边的权值: \n"; std: : cin>>vi>>vj>>weight; i=LocateVex(G,vi); j=LocateVex(G,vj); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->weight=weight; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; if(G.kind==2) { q=(ArcNode*)malloc(sizeof(ArcNode)); q->adjvex=i; q->weight=p->weight; q->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=q; } } } intMinEdge(WeightTypelowcost[],intvexmun) { inti,k; WeightTypej; k=0; while(lowcost[k]==0) { k++; } j=lowcost[k]; for(i=k+1;i { if(lowcost[i]! =0&&lowcost[i] { j=lowcost[i]; k=i; } } returnk; } voidPrim(ALGraphG,intv0,intadjvex[]) { WeightTypelowcost[MAX_VERTEX_NUM]; inti,k; ArcNode*p; for(i=0;i { if(i! =v0) { lowcost[i]=999; adjvex[i]=v0; } } p=G.vertices[v0].firstarc; while(p) { lowcost[G,p->adjvex]=p->weight; p=p->nextarc; } lowcost[v0]=0; for(i=0;i { k=MinEdge(lowcost,G.vexnum); if(k>=G.vexnum) return; std: : cout<<"("< lowcost[k]=0; p=G.vertices[k].firstarc; while(p) { if(p->weight { adjvex[p->adjvex]=k; lowcost[p->adjvex]=p->weight; } p=p->nextarc; } } } intmain() { intadjvex[MAX_VERTEX_NUM]; ALGraphG; G.kind=2; CreateGraph(G); Prim(G,0,adjvex); return0; } /*测试数据 9152 A B C D E F G H I AB32.8 AI18.2 AH12.1 AC44.6 BC5.9 CD21.3 CE41.1 CG56.4 DE67.3 DF98.7 EF85.6 EG10.5 HG52.5 IH8.7 IF79.2 */ 页脚内容
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管道铺设施工的最佳方案 完整程序代码 管道 铺设 施工 最佳 方案 完整 程序代码