最有旅行路线‘.doc

实用标准文案 精彩文档 问题描述： 给定一张航空图，图中顶点代表城市，边代表2城市间的直通航线。现要求找出一条满 足下述限制条件的且途经城市最多的旅行路线。(1)从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点(可途经若干城市)。(2)除起点城市外，任何城市只能访问1次。编程任务：对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。数据输入：由文件input.txt提供输入数据。文件第1 行有2个正整数N 和V，N 表示城市数，N100，V 表示直飞航线数。接下来的N行中每一行是一个城市名，可乘飞机访问这些城市。城市名出现的顺序是从西向东。也就是说，设i,j 是城市表列中城市出现的顺序，当ij 时，表示城市i 在城市j 的东边，而且不会有2 个城市在同一条经线上。城市名是一个长度不超过15 的字符串，串中的字符可以是字母或阿拉伯数字。例如，AGR34或BEL4。再接下来的V 行中，每行有2 个城市名，中间用空格隔开，如 city1 city2 表示city1到city2 有一条直通航线，从city2 到city1 也有一条直通航线。结果输出:程序运行结束时，将最佳航空旅行路线输出到文件output.txt 中。文件第1 行是旅行路线中所访问的城市总数M。接下来的M＋1 行是旅行路线的城市名，每行写1 个城市名。首先是出发城市名，然后按访问顺序列出其它城市名。注意，最后1行（终点城市）的城市名必然是出发城市名。如果问题无解，则输出“No Solution!”。输入示例 ? ? ? ? ? ? ? ? ? ? ? ? ?输出示例8 9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 7Vancouver ? ? ? ? ? ? ? ? ? ? ? ?VancouverYellowknife ? ? ? ? ? ? ? ? ? ? ?EdmontonEdmonton ? ? ? ? ? ? ? ? ? ? ? ?MontrealCalgary ? ? ? ? ? ? ? ? ? ? ? ? ? ??HalifaxWinnipeg ? ? ? ? ? ? ? ? ? ? ? ? ?TorontoToronto ? ? ? ? ? ? ? ? ? ? ? ? ? ??WinnipegMontreal ? ? ? ? ? ? ? ? ? ? ? ? ??CalgaryHalifax ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??VancouverVancouver EdmontonVancouver CalgaryCalgary WinnipegWinnipeg TorontoToronto HalifaxMontreal HalifaxEdmonton MontrealEdmonton Yellowknife Edmonton Calgary 分析： 这题建网络流模型比较简单，就是求出两条最长不相交的增广路。最大费用最大流可解，除了起点和终点每个点容量为1，起点终点容量为2，这样就可以限制每个点只能取一次。点的容量如何为1和2呢，之前有说过，把一个点拆成2个点，2点之间加边，权值为1或者2即可。对于每条航线，只要增加从西到东的航线就行了，因为给出2个城市不一定是从西向东的顺序，因此要判断一下，航线容量为1，费用为0。值得注意的是起点和终点城市容量为2，在极端情况下只有2个城市a,b，如果容量为1就错了，因为可以这样的情况：a-b-a。求一次最大费用流就可以了。起点是1，终点是n。因为求出的是最大流，所以保证在可能的情况下流量一定为2，如果流量为1或者0，则No Solution!。 可以转化为最小费用流，方法很简单就是把费用从正变为负，这样求出的最小费用取负就是最大费用流。求增广路还是用spfa。 有人会疑惑，不是从西到东再到西么。换个角度想就是2条从西向东的路，起点终点相同。 不过打印路线还是比较麻烦的，用一个visit数组判断是否打印过这个点，因为一共有2条路线。具体的看代码实现吧。 代码： [cpp] HYPERLINK /dieyidezui/article/details/8769283 \l # \o view plain view plain HYPERLINK /dieyidezui/article/details/8769283 \l # \o copy copy HYPERLINK /dieyidezui/article/details/8769283 \l # \o print print HYPERLINK /dieyidezui/article/d