网络流24题-洛谷P2770 航空路线问题

题目描述

给定一张航空图,图中顶点代表城市,边代表 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 个城市名,中间用空格隔开,如 city1 city2 表示 city1到 city2 有一条直通航线,从 city2 到 city1 也有一条直通航线。

输出格式:

件第 1 行是旅行路线中所访问的城市总数 M。 接下来的 M+1 行是旅行路线的城市名,每行写 1 个城市名。首先是出发城市名,然后按访问顺序列出其它城市名。 注意,最后 1 行(终点城市)的城市名必然是出发城市名。如果问题无解,则输出“No Solution!”。

输入输出样例

输入样例#1:

输出样例#1:

说明

感谢 @FlierKing 提供spj

既然航线都是双向的,那问题可以转化成从起点1找两条不相交的最长路径到N,使用最大费用最大流即可。

首先,为了保证每个点只经过一次,还是采用经典做法–拆点。将一个点i拆成两点<i.A>和<i.B>,将其用一条容量为1,费用为1的边连接起来,容量为1限制了只选1次,费用为1代表选了它之后旅行城市+1。特别地,因为源点1与汇点N同时在两条路径上,因此它们的<1.A> <1.B>和<N.A><N.B>之间的容量要设为2,费用还是1。对于原图中的边(航线),依照自西向东的方向连边,也就是说对于i<j,从<i.B>到<j.A>连接一条容量为1,费用为0的边。(容量似乎可随意,只要非零,因为从B点出来的边最大流量一定是1),跑一次最大费用最大流,答案就是最大费用-2。为什么要-2呢?注意到我们源点1与汇点N的容量是2,也就是说我们重复地计算了一次源点和汇点(因为它们同时存在于两条路线上),因此减掉2。

至于No Solution的情况,看一下最大流是不是2就行了,不是2说明找不到两条路嘛。

但是,这样做只能得到91分,第二个测试点十分坑爹!因为我们上述建图的条件是得有两条路吧,有一个极端情况:如果只能1->n->1这样走,显然是满足题意的,但是这么算下来因为只有一条路所以算法会输出No Solution!因此,对于这种情况要特判一下才行,佛了。

代码:

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*