7高铁修建最经济方案设计

高铁修建最经济方案设计一、工程描述图7-1所示的图中顶点表示城市，边表示两个城市之间修建高铁需要的费用(单位：n亿)，假设城市之间没有修建任何高铁，那么为了把n个城市连接起来，最多可修建n(n-l)/2条高铁，最少可修建n-1条高铁。如果考虑修建造价，而且还要保证每两个城市都可连通,那么如何选择n-1条高铁线路，使得修建高铁的总造价最小呢？二、工程分析修建所有城市间高铁的费用预算后，为了降低本钱节省费用，要设计最经济的建设方案,应该尽量减少修建高铁的条数，但又要保证所有城市.都能连通，那么必须修建n-1条高铁线路，而且总费用还要最低。在此我们通过普里姆方法生成最小生成树来实现高铁修建最经济方案。普里姆方法生成最小生成树的过程如图7-16所示，在此不再介绍具体过程。具体算法如下，首先，采用邻接矩阵方法存储图，然后，定义一个辅助数组，用来存储从U集合中某顶点出发到其他顶点边上的权值，以及存储该边依附在U中的顶点下标，最后，实现普里姆方法生成最小生成树的算法。三、工程实现^include"stdio.h”ttdefincMAX1000〃单位百亿元typedefstruct(charvcxs[10][8J;〃存放城市名称，最多含10个城市intedges[l0][10];//存储每条高铁建设费用intn,e;//分别代表图的顶点数和边数}Mgraph;structintlowcost;〃存储该边上的权值intvex;〃存储该边依附在U中的顶点下标}CloseEdge[10];〃辅助数组〃创立高铁建设网voidGreateMGraph(Mgraph*G)(inti,j,k,w;printfC请输入城市个数和修建的高铁条数:")；scanfC%d,%d",&G->n,&G->e);for(i=0;i<G->n;i++)(printf("请输入第%d个城市名称:"，i+1);scanf("%s”,G~>vexs[i]);)printfC各城市序号为：\n");for(i=0;i<G~>n;i++)printf(，，%s:%d\t/，,G->vexs[i],i+1);printf("\n");for(i=0;i<G->n;i++)〃邻接矩阵初始化(for(j=0;j<G->n;j++)G->edges[i][j]=MAX;〃假设建设费用为最大G->edges[i][i]=0;〃到本身的费用为0)for(k=0;k<G->e;k++)//建立邻接矩阵(printf("请输入建设第%d条高铁两个城市序号及建设费用：",k+1);scanf("%d,%d,",&i,&j,&w);//输入边的一对顶点序号G->edges[i-l][jT]=w;G->edges[j-l][iT]=w;}}〃求最小距离值，返回下标intMinValue(intn)intj,k;for(j=0;j<n;j++)if(CloseEdge[j].lowcost>0)k=j;break;}for(j=0;j<n;j++)if(CloseEdgefj].lowcost〉0&&CloseEdge[j].lowcost<CloseEdge[k].lowcost)k=j;returnk;)〃普里姆方法构建最小生成树voidPrim(Mgraph*G,intu)(intcc=0,pp[20];//pp记录最小生成树中边的下标intk=0,i,j,si;for(i=0;i<G->n;i++)(CloscEdgc[i].vex=u;CloseEdge[i].lowcost=G->edges[u][i];}CloscEdgc〔u].lowcost=0;for(i=l;i<G->n;i++)〃最小生成树的G->n-l条边(k=MinValue(G~>n);sl=CloscEdge[k].vex;〃边(si,k)是一条权值最小的边CloseEdge[k].lowcost=0;//将顶点k加入到U中pp[cc++]=sl;pp[cc++]=k;for(j=0;j<G->n;j++)if(G->edges[k][j]<CloseEdge[j].lowcost)CloscEdgc[j].lowcost=G->edges[k][j];CloseEdgetj].vex=k;)}printfC®铁建设最经济方案为:\n");for(i=0;i<2*(G->n-l);i=i+2)printfC应建设高铁:%s<=>%s,费用:％d\n”,G->vexs[pp[i]],G->vexs[pp[i+1]],G->edges[pp[i]][pp[i+1]]);}main()(MgraphG;GreateMGraph(&G);Prim(&G,0);四、结果验证"0\李刚-味结构'盖教社出版\源代码演7童图的结构分析与应...叵）1请输入城市个数和修建的高铁条数:5,8请输入第1个城市名称:A请输入第2个城市名称:B请输入第3个城市名称:C请输入第4个城市名称:D请输入第5个城市名称:E各撮市序号为：A:1B:2C:3D:4E:5请输入建设第1条高铁两个城市序号及建设费用：1,2,5请输入建设第2条高铁两个城市序号及建设费用:1,3,1请输入建设第3条高铁两个城市序号及建设费用：1,4,6请输入建设第4条高铁两个城市序号及建设费用:2,3,4请输入建设第5条高铁两个城市序号及建设费用:3,4,7请输入建设第6条高铁两个城市序号及建设费用:3,5,3请输入建设第7条高铁两个