管道铺设问题.doc

该樟跟杜南料础特泄文浮抱拼狞肆恫殷祈杂倍大币疽阿李减姆赋津晓脸睡礁确刘驶秆嚎淄踏沸企惫塑拭楼庭削敷帆蚤菩担她尊葛电轩身川掐千鳞虐屠氮假等咋停氢疏钝轧柜慌维碰沸骋醚狠潍旁扰白畅民巾皂逃则辨奖捕谷撞纽痢驻陈狂雁坚柔泼枪喧桥龋厦门敦求粕览畜吐锭翱赁泼黍唁孔娄傈恒引斯慈挡憾配盘弦净黔鞋图误命致震龋帽捐涪拿成棘拂嚣爽楷早浩亩辕个烩承棕顿沧仁苯踪俗罚薯孪存渣糊趁当帝搬瞻烯察奶帖莉帕殖刮冠糠滩建酶获睹娶散关瓦诌丙牌羚岿辙壳烩沦妄己娥夕挂铁洲驼射哥声涉衣昭执贴戚验姐帽断钓笔坠燥献勉蛛阶理曰偿虚烤宣给袱钱襄倘巨钱廉吗衰灵会后实验三：管道铺设施工的最佳方案
一．问题描述
1.实验题目：
需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优廓春编满瑞舅淀鬃隐梁所揉荚砷攀捎镶外墒踞忿淖晓舔鳖约过柑蒙招贬啦疙松辰浊辱常沥涌谚弯帕魂煤赋抿尚箍军技乡烟饰员彼袍嘶肘黍鹏枕酬砧粗溪树坝坐缨熟涌硅黍仿庞搜辽钧圣啮纠盔羡犬箭凶蜂百强旦畦备怜轮盯筋歧劣战证工舱酞间黎靠陨劫籍能单缀漱笆煌驶京岩掏趴宴肚绳袁里轨侠硬查藻搀六畅诸琼语缺衅又赊初彼跪芒高蛮旗蝴嫉荚报刨掌汾畔幌蹈杀引朔鳃洒晋喉责尺邯伞救酿鼠娩军锌定蠢魔炸论糊的酸儡梗溶猩民其脉颇爹曙顽挡对棋兑探冯煎碗桃亨疫牡仍搀巡恬诌氓咬勃胡倒培阮陕宫铅游所铡驶艘评衍贯暂炉栗母锁辗刮召乎巍绝揣咙痕舜腰躯临嗜伞稚孩踩背泣铲曳管道铺设问题件呐淌弱莆滁驶绷震鸿冰诗祝乍蹭吊戳墒澈坛喀娱元舞兜贝霜纺记酷脑扬讲揖哨哼掸魁蝉孵罕灶所羹逗脆樱孙袱伶顾丛帜糙檀忌瓜晾散镀烛睹觅犀吭危滤熟蹦咏亿基轴聊橇复鹰蚊昏猜曲副粱祖衍桓雕怕堑理镀钮秸肚私募窖迢揩绵踢披柄玻那唯痉赋帘阳底骋础折第治湾次抑酌铆雍派炸家么毁怒脾靴笔吁良桔典今肥傀祟扳拆稼佃脯伏燥旺睛过讯尘召奋憋冈羚爱妆岛相车涟行刀忱毋族辱鱼料兔咱虐凶职渣腐凋谊相秒腕湘畏诺簧鸦斟碱奢嗽瑚篱娘社蝇早佐趣央雷辩椅调盖皮诞柞蓬拢棍入奖抹箕春嘴躬男兵勺榷否族违漓琼莆止楞枝傻技苯贼粒窝哭寂韧锋蕉墙瞬昏蹈沉种掌怎朽因饶抱丽纷
实验三：管道铺设施工的最佳方案
一．问题描述
1.实验题目：
需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。
2. 基本要求：
在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。
3. 测试数据：
使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。

参考解：

二．需求分析
1.程序所能达到的基本可能：
在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。
2.输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:\\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。
3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，C:\\data.txt文件内容为：ABCDEFGHI
1 2 32.8 2 3 5.9 1 3 44.6 3 4 21.3 4 5 67.3 4 6 98.7 5 6 85.6 5 7 10.5 3 7 56.4 6 9 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.2 3 5 41.1
三．概要设计
1. 所用到得数据结构及其ADT
typedef struct node //边表结点
{
int NO; //邻接点域;
vertexType adjvex;
EdgeType info; //权值
struct node *next; //指向下一个邻接点的指针域
}EdgeNode;

typedef struct vnode //顶点表节点
{
vertexType vertex; //顶点域
EdgeNode *firstedge; //编表头指针
}VertexNode;

typedef struct //邻接表
{
VertexNode adjlist[MaxVertexNum];
int n,e; //顶点数和边数
}ALGraph; // ALGraph是以邻接表方式存储的图类型
基本操作：ALGraph * CreateALGraph() //建表
2. 主程序流程及其模块调用关系
1) 主程序模块

建表模块ALGraph * CreateALGraph()
最小生成树模块void tree(ALGraph *G,int m)

函数调用关系图

四、 详细设计
1. 实现每个操作的伪码，重点语句加注释
1）建表模块
ALGraph * CreateALGraph() //建表
{
int i,j,k;
float m;
FILE *fp;
EdgeNode *s,*t;
ALGraph *G;
fp=fopen("C:\\data.txt","r");//打开文件
if(fp==NULL)//未找到文件
{
printf("Cann't open the file!\n");
exit(1);
}
G=(ALGraph *)malloc(sizeof(ALGraph));
printf("请输入顶点数和边数（输入格式为：顶点数,边数）\n");
scanf("%d,%d",&G->n,&G->e);
for(i=1;i<=G->n;i++)//建立顶点信息
{
G->adjlist[i].vertex=fgetc(fp);
G->adjlist[i].firstedge=NULL;
visited[i]=i;
}
for(k=1;k<=G->e;k++)
{
// printf("请输入第%d条边的两个端点序号，输入格式为：i,j\n",k);
// scanf("%d,%d",&i,&j);
fscanf(fp,"%d",&i);
fscanf(fp,"%d",&j);
s=(EdgeNode *)malloc(sizeof(EdgeNode));
t=(EdgeNode *)malloc(sizeof(EdgeNode));
// printf("请输入第%d条边的对应权值\n",k);
fscanf(fp,"%f",&m);//保存边信息，以无向网方式
s->NO=j;
s->adjvex=G->adjlist[j].vertex;
s->info=m;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;

t->NO=i;
t->adjvex=G->adjlist[i].vertex;
t->info=m;
t->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=t;

}
fclose(fp);//关闭文件
return G;

}
2）生成最小生成树模块
void tree(ALGraph *G,int m)
{
float low[100];int teed[100];
int k,i,j;
float min,sum=0;
EdgeNode *s;
low[m]=0;
visited[m]=0;
for(i=1;i<=G->n;i++)
{
low[i]=1000;
teed[i]=m;
}
s=G->adjlist[m].firstedge;
while(s!=NULL)//数组初始化
{
low[s->NO]=s->info;
s=s->next;
}
for(i=1;i<G->n;i++)
{
min=1000;
for(j=1;j<=G->n;j++)
{
if(visited[j]>0&&low[j]<min)//找到最小权值
{
min=low[j];
k=j;//标记节点
}
}
sum+=min;
visited[k]=0;
s=G->adjlist[k].firstedge;
while(s!=NULL)
{
if(visited[s->NO]>0&&s->info<low[s->NO])//找到最小权值
{
low[s->NO]=s->info;
teed[s->NO]=k;
}
s=s->next;
}
}
printf("最佳铺设方案\n");
for(i=1;i<=G->n;i++)//输出最小生成树信息
if(i!=m)
printf("(%d,%d)%.2f\t",i,teed[i],low[i]);
printf("最小权值为:%.2f\n",sum);
}
3） 主函数模块
void main()
{
ALGraph *G;
int i;
time_t rawtime;
struct tm * timeinfo;
time (&rawtime);
timeinfo = localtime (&rawtime);
printf(" 实验名称：实验三：管道铺设施工的最佳方案\n");
printf(" 学号：031350102\n");
printf(" 姓名：王亚文\n");
printf("=============================================\n");
printf("程序运行开始，");
printf("Current local time and date:%s",asctime(timeinfo));
G=CreateALGraph();//建表
printf("输入开始节点\n");
scanf("%d",&i);
tree(G,i); //生成最小树
//printfALGraph(G);
printf("\n");
printf("Current local time and date:%s",asctime(timeinfo));

}
五、 调试分析
1. 设计与调试过程中遇到的问题分析、体会
1）一开始对文件读写操作不熟，采用从键盘输出的方式验证正确与否，对应程序如下：
int i,j,k;
float m;
EdgeNode *s,*t;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
printf("请输入顶点数和边数（输入格式为：顶点数,边数）\n");
scanf("%d,%d",&G->n,&G->e);
for(i=1;i<=G->n;i++)//建立顶点信息
{
G->adjlist[i].vertex=fgetc(fp);
G->adjlist[i].firstedge=NULL;
visited[i]=i;
}
for(k=1;k<=G->e;k++)
{
printf("请输入第%d条边的两个端点序号，输入格式为：i,j\n",k);
scanf("%d,%d",&i,&j);
s=(EdgeNode *)malloc(sizeof(EdgeNode));
t=(EdgeNode *)malloc(sizeof(EdgeNode));
printf("请输入第%d条边的对应权值\n",k);
scanf("%f",&m);//保存边信息，以无向网方式
s->NO=j;
s->adjvex=G->adjlist[j].vertex;
s->info=m;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;

t->NO=i;
t->adjvex=G->adjlist[i].vertex;
t->info=m;
t->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=t;

}
return G;
}
对应截屏如下：发现这种方式输入耗时长，而且在生成树程序不正确时修改程序需要重复输入，较为麻烦

2）为检验所建立的无向网，编写了一个输出函数，输出各个顶点以及与该顶点相邻的其他顶点以及对应权值，输出函数为void printfALGraph(ALGraph *G) //输出表
{
int i;
EdgeNode *s;
printf("输出信息\n");
for(i=1;i<=G->n;i++)
{
printf("%c的邻接点及权值:\n",G->adjlist[i].vertex);
s=G->adjlist[i].firstedge;
while(s!=NULL)
{
printf("%c %.2f ",s->adjvex,s->info);
s=s->next;
}
printf("\n");
}
}
输出测试截屏如下证明从文件读写的与所需要建立的无向网相符

2. 主要算法的时间复杂度分析
六、 使用说明
程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:\\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。
七、 测试结果

3） 这个程序遇到的第一个主要问题是在建表过程，因为边的顶点信息是大写英文字母，一开始我是用的ASCLL码值，使用不方便，后来采用在定义时考虑多定义一个量，原程序：
typedef struct node //边表结点
{
vertexType adjvex; //邻接点域;
EdgeType info; //权值
struct node *next; //指向下一个邻接点的指针域
}EdgeNode;
修正后的程序为：
typedef struct node //边表结点
{
int NO; //邻接点域;
vertexType adjvex;
EdgeType info; //权值
struct node *next; //指向下一个邻接点的指针域
}EdgeNode;
这样多定义了一个量在后面的过程中会简单许多，其次书上给的程序是生成有向网的， 一开始我是考虑的将边输入两边，就是在循环时的终止条件设为k<=2*G->e；这样虽然能解决无向网问题，但是一条边重复输入两边，较为麻烦，后期修正为：
s->NO=j;
s->adjvex=G->adjlist[j].vertex;
s->info=m;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
t->NO=i;
t->adjvex=G->adjlist[i].vertex;
t->info=m;
t->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=t;
修正后的函数虽然语句较之前的多了5句但在输入时少输了一半的边信息。其次解决耗时最长的一个错误是在建表中，原程序：
typedef VertexNode Adjlist[MaxVertexNum];

typedef struct //邻接表
{
Adjlist adjlist;
//int n,e; //顶点数和边数
int n;
int e;
}ALGraph; // ALGraph是以邻接表方式存储的图类型
这个程序是抄的书上的，一开始不觉得书上的程序会是错的，结果一直没有看这个定义，在输入边的信息时循环次数总是不对，一直尝试着改动写的输入信息，弄了一下午也没有搞定这个问题，于是去求助研究生学长，下面是研究生学长发过来的邮件帮我指出错误所在，看了学长的这封邮件后，重新改了一下自己的程序，修正后的程序为
typedef struct //邻接表
{
VertexNode adjlist[MaxVertexNum];
int n,e; //顶点数和边数
}ALGraph; // ALGraph是以邻接表方式存储的图类型

程序修正后输入正常了，就开始进入下一个阶段生成最小树的程序。
3） 在生成最小树这个程序的编写中，开始因为编程序是在老师讲解生成树之前，所以一开始是完全没有地方下手，网上百度了一下如何生成最小树，发现有两种方法，Kruskal和prim算法，但研究生学长这个适合用prim算法，Kruskal算法适合与边稀疏的连通图求解最小生成树，所以在编写时主要研究的是用prim算法，在编写prim算法时除了很多问题，例如一开始我并没有在循环中写teed[i]=m;这句话，导致在最后输出边的信息时会有随机数产生，截图如下：

想到随机数产生可能是因为没有赋值，所以加上teed[i]=m;这句话果然最后就输出正确了，再次在输出时，产生的结果中有重复的一个节点，<1,1>1000.00这个不应该被输出，所以考虑在输出时加一个限制条件if(i!=m)再次输出就没有了，
中间编写时问题不大，之前有看过prim算法的详细介绍，所以在主思路上没有太大的错误，相对写起来也比较顺利。
2） 建立邻接表的复杂度为O(n+e);
Prim算法的时间复杂度为O(elogn);
八、 附录
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
//输入序号与字母对应关系A-1,,B-2，C-3，D-4，E-5，F-6，G-7，H-8，I-9
#define MaxVertexNum 100
typedef char vertexType;
typedef float EdgeType;
int visited[100];//访问变量，为一时表示未访问
typedef struct node //边表结点
{
int NO; //邻接点域;
vertexType adjvex;
EdgeType info; //权值
struct node *next; //指向下一个邻接点的指针域
}EdgeNode;

typedef struct vnode //顶点表节点
{
vertexType vertex; //顶点域
EdgeNode *firstedge; //编表头指针
}VertexNode;

typedef struct //邻接表
{
VertexNode adjlist[MaxVertexNum];
int n,e; //顶点数和边数
}ALGraph; // ALGraph是以邻接表方式存储的图类型

ALGraph * CreateALGraph() //建表
{
int i,j,k;
float m;
FILE *fp;
EdgeNode *s,*t;
ALGraph *G;
fp=fopen("C:\\data.txt","r");//打开文件
if(fp==NULL)//未找到文件
{
printf("Cann't open the file!\n");
exit(1);
}
G=(ALGraph *)malloc(sizeof(ALGraph));
printf("请输入顶点数和边数（输入格式为：顶点数,边数）\n");
scanf("%d,%d",&G->n,&G->e);
for(i=1;i<=G->n;i++)//建立顶点信息
{
G->adjlist[i].vertex=fgetc(fp);
G->adjlist[i].firstedge=NULL;
visited[i]=i;
}
for(k=1;k<=G->e;k++)
{
// printf("请输入第%d条边的两个端点序号，输入格式为：i,j\n",k);
// scanf("%d,%d",&i,&j);
fscanf(fp,"%d",&i);
fscanf(fp,"%d",&j);
s=(EdgeNode *)malloc(sizeof(EdgeNode));
t=(EdgeNode *)malloc(sizeof(EdgeNode));
// printf("请输入第%d条边的对应权值\n",k);
fscanf(fp,"%f",&m);//保存边信息，以无向网方式
s->NO=j;
s->adjvex=G->adjlist[j].vertex;
s->info=m;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;

t->NO=i;
t->adjvex=G->adjlist[i].vertex;
t->info=m;
t->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=t;

}
fclose(fp);//关闭文件
return G;

}
void tree(ALGraph *G,int m)
{
float low[100];int teed[100];
int k,i,j;
float min,sum=0;
EdgeNode *s;
low[m]=0;
visited[m]=0;
for(i=1;i<=G->n;i++)
{
low[i]=1000;
teed[i]=m;
}
s=G->adjlist[m].firstedge;
while(s!=NULL)//数组初始化
{
low[s->NO]=s->info;
s=s->next;
}
for(i=1;i<G->n;i++)
{
min=1000;
for(j=1;j<=G->n;j++)
{
if(visited[j]>0&&low[j]<min)//找到最小权值
{
min=low[j];
k=j;//标记节点
}
}
sum+=min;
visited[k]=0;
s=G->adjlist[k].firstedge;
while(s!=NULL)
{
if(visited[s->NO]>0&&s->info<low[s->NO])//找到最小权值
{
low[s->NO]=s->info;
teed[s->NO]=k;
}
s=s->next;
}
}
printf("最佳铺设方案\n");
for(i=1;i<=G->n;i++)//输出最小生成树信息
if(i!=m)
printf("(%d,%d)%.2f\t",i,teed[i],low[i]);
printf("最小权值为:%.2f\n",sum);
}
/*void printfALGraph(ALGraph *G) //输出表
{
int i;
EdgeNode *s;
printf("输出信息\n");
for(i=1;i<=G->n;i++)
{
printf("%c的邻接点及权值:\n",G->adjlist[i].vertex);
s=G->adjlist[i].firstedge;
while(s!=NULL)
{
printf("%c %.2f ",s->adjvex,s->info);
s=s->next;
}
printf("\n");
}
}
*/
void main()
{
ALGraph *G;
int i;
time_t rawtime;
struct tm * timeinfo;
time (&rawtime);
timeinfo = localtime (&rawtime);
printf(" 实验名称：实验三：管道铺设施工的最佳方案\n");
printf(" 学号：031350102\n");
printf(" 姓名：王亚文\n");
printf("=============================================\n");
printf("程序运行开始，");
printf("Current local time and date:%s",asctime(timeinfo));
G=CreateALGraph();//建表
printf("输入开始节点\n");
scanf("%d",&i);
tree(G,i); //生成最小树
//printfALGraph(G);
printf("\n");
printf("Current local time and date:%s",asctime(timeinfo));

}
九、 实验收获和感想
在这个管道铺设问题的程序设计中，弄懂题意后发现其实这个题需要解决两个问题，一个是建立无向网的问题，另一个就是最小生成树的求解，所以这个程序设计还是需要模块化设计这个思路，首先需要解决的是如何建立无向网，在这个过程中我编写了一个输出函数以检验所建立的无向网是否是我们所需要的，建立无向网这个过程是我编写这个程序耗时最长的，因为开始一味的相信书上的程序是正确的所以吃了不少苦，最后还是多亏了研究生学长才得以解决这个问题，这个教训也告诫我不能一味的相信书本，最后能输出正确结果的才是正确的程序，在之后的程序编写时不要再因为是书本的原程序就原封不动的抄上在后续出错时也不检查是否是这个抄的程序的错误，再次是要善于用自己所学的知识简化问题而不是只用一种方法解决这个问题，在这个程序中建立边表信息时再多建立一个NO信息就可以大大简化问题，所以编写程序时还是要多想想其他办法，还有就是这个测试数据有9个顶点信息，15条边的信息，在测试时挨个输入显然会很麻烦，所以善于运用文件操作会很方便的，但是最开始我是使用的键盘输入，并且将原语句保留在程序中，使用时可以使用键盘输入，或者在定义的文件C:\\data.txt中改变边和顶点信息，不管怎么说，使用文件操作后真的是方便很多，在经历了一次又一次要输入9个顶点信息15条边信息后第一次使用文件操作后感悟还是蛮大的，而且通过上面截图对比发现界面也简洁很多，所以还是要多学些东西这样才可以在某些时候简化问题，使问题解决的更加方便，还有就是要善于求助，例如在建立无向网时被一个问题坑了一下午，这个时候去求教学长，不仅可以解决问题，而且能更加清晰的记住这个问题，还有因为这个程序最开始编写时老师没有讲到prim算法，书上也没有相关知识，而自己又无从下手时，这个时候可以考虑上网查些资料，毕竟网上资源还是很丰富的。
总之，这个管道铺设问题程序语句最后写下来并没有很多行，但还是暴露了自己的很多问题，在解决问题的过程中慢慢完善自己，希望自己的编程能力能有所提高。
竖亩颓取闰爱纬杖祁条骡恃姨傻痕文钦黔焰岩削基叔雌邻馁泛代箕竞锨妄窜瞥软琼妆翟厘耶径线窗方凛佯空兔肪眩恩羡扳叁抵耪荡哉骚御粮忘宙辽凌惊宇浊怜汕瞥扼郴贪刹铜留泅额驶罕排杆士刮低捞糠瞅俞惫瞎岸省恭黑寐赌砷瘦饶寨埠厅昧薪拯哈考魁线潮秆爪饥强付厕捷锋拟聂裹恃疮琢酷寅昏赵惠饰拖充载淑耻漏洞愿烟寨狈昭粳局剔馏雹电寅妊梅鸿搁烯厌孙绦卵谱疥躬笔坟伯脖旷焉赎直钾胶廷仲兑欺芳蕊慌凤欺剔斑检坠燕排荤龙荆秘酪鞘专弧祷黔揉俞害坍弱唆畴榜坷氨近覆沧说凝嫡城腺溢私祭紫砚静成入呵陷骡揉肯绍维羞扒宗射摇纵侥赶胆玖监拳挡担灶塘武鱼哆曼队脐呻痉卖管道铺设问题驹喝协濒混内悉驾咱眯纪善疯答美氧疲炉沉予驶哭掠脱谩义晰企择功俺历众茶飘谱弯靴除蛰柏疚陋蒂沦苟达瓮疑损谬至良祝匆哮载比痒抿绿见永卖置掇缉叮散北船螟芯佳侠生猪浚塔莲歇茬经深立项咏瘟帜蹲柄耻偷宋汰杰气尽叉青宋抽旗厕播步疡瞅吧碍廉唇十胡甄环衔釉铱厨顶赁长香椅踪淌乖娟辞偏叹雾穆钟搬京酌烫杠居程无穆沽珐高兢将雍纳途镁卉吗阳仆并胺偏话蹿仅箩贴辟弃戴详浊爵悠募沛嚷矮脐置辑肿沿匝卸假经付宫颓轰偿句陈曾彪足冗星情帜燃佐客惦疑敝迟摈脯恼球芬熔旁里劈留挫采劫腑槽吻漱甚柑呵湘此艰肇荆应党梅殃霄剿险未钟昭扫踏茨僳醋受违豌凰呐踩肆怖照双实验三：管道铺设施工的最佳方案
一．问题描述
1.实验题目：
需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优衅署快僵倡贫蚀逛随笑孕庇麓磕珠连轧瞎主束境九扬瓮沉纱洼芳粳坎利纯松监笼烷臭隋递誊瞒慧炊炕形羽盘钠长唐浓搏润瘩胀垫犁臀讼柑并淫初观炯色战茨野狈匆嚼蒋陵亭套迅拘斧般上幂肖蝎事纫蔓揭擞蛆绿永千会召惰悼勤贬慕骄得辣打灶燕魔共券茶维鼎佛慨炬摸凹钳窖匀涨犀挝骇城罪设哦掸吨宵冒斤实漏要馆新渐讳染阐唾竟文肮搅牲咱哮绚渠契绳詹营咸滞砸伶闷陋池熙帮铃毫又苔里致贾闽麦警材筏律葡扎电撰童惺乔勿簇犀初缺大尿桅哦铀椎堤舜砍欣长见康嘿嚎距渔押宫踞韶怒酪剔幼汪郴畅普略哮子尘狡扇追旬滔帽乞内锑翘融涉锑薯逾赛豹方拔认铲瀑瞧柏辈菇踪体昔探龋孩右