最有旅行路线‘.doc

问题描述:给定一张航空图,图中顶点代表城市,边代表2城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。(1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。(2)除起点城市外,任何城市只能访问1次。编程任务:对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。数据输入:。文件第1行有2个正整数N和V,N表示城市数,N<100,V表示直飞航线数。接下来的N行中每一行是一个城市名,可乘飞机访问这些城市。城市名出现的顺序是从西向东。也就是说,设i,j是城市表列中城市出现的顺序,当i>j时,表示城市i在城市j的东边,而且不会有2个城市在同一条经线上。城市名是一个长度不超过15的字符串,串中的字符可以是字母或阿拉伯数字。例如,AGR34或BEL4。再接下来的V行中,每行有2个城市名,中间用空格隔开,如city1city2表示city1到city2有一条直通航线,从city2到city1也有一条直通航线。结果输出:程序运行结束时,。文件第1行是旅行路线中所访问的城市总数M。接下来的M+1行是旅行路线的城市名,每行写1个城市名。首先是出发城市名,然后按访问顺序列出其它城市名。注意,最后1行(终点城市)的城市名必然是出发城市名。如果问题无解,则输出“NoSolution!”。输入示例             输出示例89                  7Vancouver            VancouverYellowknife           EdmontonEdmonton            MontrealCalgary               HalifaxWinnipeg             TorontoToronto               WinnipegMontreal              CalgaryHalifax                VancouverVancouverEdmontonVancouverCalgaryCalgaryWinnipegWinnipegTorontoTorontoHalifaxMontrealHalifaxEdmontonMontrealEdmontonYellowknifeEdmontonCalgary分析:这题建网络流模型比较简单,就是求出两条最长不相交的增广路。最大费用最大流可解,除了起点和终点每个点容量为1,起点终点容量为2,这样就可以限制每个点只能取一次。点的容量如何为1和2呢,之前有说过,把一个点拆成2个点,2点之间加边,权值为1或者2即可。对于每条航线,只要增加从西到东的航线就行了,因为给出2个城市不一定是从西向东的顺序,因此要判断一下,航线容量为1,费用为0。值得注意的是起点和终点城市容量为2,在极端情况下只有2个城市a,b,如果容量为1就错了,因为可以这样的情况:a->b->a。求一次最大费用流就可以了。起点是1,终点是n。因为求出的是最大流,所以保证在可能的情况下流量一定为2,如果流量为1或者0,则NoSolution!。可以转化为最小费用流,方法很简单就是把费用从正变为