题目描述

给定一张航空图,图中顶点代表城市,边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

(1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。

(2)除起点城市外,任何城市只能访问 1 次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。


好麻烦的字符串处理…

solution

因为每个点有访问限制,那么把每个点拆成两个点在之间连上一条容量为1,费用为1的边

对于1和n,连上一条容量为2,费用1的边,因为可以走两次

每个点的出点和下一个的入点连上容量为1费用为0的边

当然对于1和n是容量为2费用为0的边

建完图后跑一遍最大费用最大流

然后两遍dfs找到路径

 


说点什么

avatar
  Subscribe  
提醒