某地区共有19个村庄,各村庄之间的距离(单位为km) 如图所示,图中每条连线表示有公路相连.现要沿公路铺设天燃气管道.铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.(1):如果每
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/18 02:44:15
某地区共有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++;
然后再递归一次