

$11.$航空路线问题

题目

给定一张航空图，图中顶点代表城市，边代表 $2$ 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。 $(1)$ 从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点(可途经若干城市)。 $(2)$除起点城市外，任何城市只能访问 $1$ 次。 对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

题解

最长不相交路径模型。 可以将题目要求（即从点 $1$ 到点 $N$， 然后回来，而不经过重复点的路径）转换一下，变成两条从点 $1$ 到点 $N$ 的没有重复点的路径。

由于每个点只能使用一次，那么我们会非常 熟练 自然的想到可以拆点，由于只能用一次，那么对于每一个点 $u​$ ，将其拆成两个点 $u_1, u_2​$， $u_1​$ 放到 $X​$ 集合中， $u_2​$ 放到 $Y​$ 集合中，然后由 $u_1​$ 向 $u_2​$ 连边 $(1, 1)​$ （特别的， $1​$ 和 $N​$ 的容量为 $2​$ ），对于原图中的边 $(u, v)​$ ，在建图时由 $u_2​$ 向 $v_1​$ 连边 $(1, 0)​$ ，然后跑一遍最大费用最大流，如果点 $1_1​$ 向 $1_2​$ 的连边不是满流就无解，注意可能要特判一下 $1->N->1​$ 的这种图。