某地区共有19个村庄,各村庄之间的距离(单位为km) 如图所示,图中每条连线表示有公路相连.现要沿公路铺设天燃气管道.铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.(1):如果每
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/17 18:08:07
![某地区共有19个村庄,各村庄之间的距离(单位为km) 如图所示,图中每条连线表示有公路相连.现要沿公路铺设天燃气管道.铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.(1):如果每](/uploads/image/z/10159015-31-5.jpg?t=%E6%9F%90%E5%9C%B0%E5%8C%BA%E5%85%B1%E6%9C%8919%E4%B8%AA%E6%9D%91%E5%BA%84%2C%E5%90%84%E6%9D%91%E5%BA%84%E4%B9%8B%E9%97%B4%E7%9A%84%E8%B7%9D%E7%A6%BB%28%E5%8D%95%E4%BD%8D%E4%B8%BAkm%29+%E5%A6%82%E5%9B%BE%E6%89%80%E7%A4%BA%2C%E5%9B%BE%E4%B8%AD%E6%AF%8F%E6%9D%A1%E8%BF%9E%E7%BA%BF%E8%A1%A8%E7%A4%BA%E6%9C%89%E5%85%AC%E8%B7%AF%E7%9B%B8%E8%BF%9E.%E7%8E%B0%E8%A6%81%E6%B2%BF%E5%85%AC%E8%B7%AF%E9%93%BA%E8%AE%BE%E5%A4%A9%E7%87%83%E6%B0%94%E7%AE%A1%E9%81%93.%E9%93%BA%E8%AE%BE%E7%AE%A1%E9%81%93%E7%9A%84%E4%BA%BA%E5%B7%A5%E5%92%8C%E5%85%B6%E4%BB%96%E5%8A%A8%E5%8A%9B%E8%B4%B9%E7%94%A8%E4%B8%BA1%E4%B8%87%E5%85%83%2Fkm%2C%E6%9D%90%E6%96%99%E8%B4%B9%E7%94%A8%E4%B8%BA2%E4%B8%87%E5%85%83%2Fkm.%281%29%3A%E5%A6%82%E6%9E%9C%E6%AF%8F)
某地区共有19个村庄,各村庄之间的距离(单位为km) 如图所示,图中每条连线表示有公路相连.现要沿公路铺设天燃气管道.铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.(1):如果每
某地区共有19个村庄,各村庄之间的距离(单位为km) 如图所示,图中每条连线表示有公路相连.现要沿公路铺设天燃气管道.铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.
(1):如果每个村庄均通天燃气,应如何铺设管道,才使总的铺设费用最少?
(2):天燃气公司决定在铺设管道前,派人先查看所有公路的状况,以便决定该公路是否可用.他们从村庄1出发,最后又回到村庄1.问他们应如何走,才使走的总路程最少?
某地区共有19个村庄,各村庄之间的距离(单位为km) 如图所示,图中每条连线表示有公路相连.现要沿公路铺设天燃气管道.铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.(1):如果每
所需变量:
建立两个结构体:
struct GONGLU{
int id_lu;//公路编号
int length;//公路的长
int id_cun;//与该公路相邻的一个村庄,为什么是一个呢?看下面
};
struct CUNZHUANG{
int id_cun;//该村庄的编号
int n;//与该村相邻的村的个数
GONGLU plu1;//与该村相邻的村的公路,
GONGLU plu2;//以及那一端的村庄.
GONGLU plu3;//第三个
GONGLU plu4;//第四个
GONGLU plu5;//好像最多五个吧
}
然后当然就是:
CUNZHUANG cun[19];
接下来就是
int arrived_cun[19];//记录路过的次数
int arrived_lu[19];
int path[40];//记录路径,路径可能重复,所以接下来还要一个变量
int repeat=0;//记录最大允许重复的次数
int best[40];//用来记录最佳路径
long money;//记录所需money;
算法:
输入输出就不废话了
寻找路径就用递归地遍历吧
基本算法是差不多的
大概是这样的:
begin
计算总共经过的村庄(公路)的次数是否大于 19+repeat
是则与最佳路径比较,否则继续
依次遍历当前村庄所连的所有公路
end
如果一次没有找出来,就:
repeat++;
然后再递归一次