计蒜客 Our Journey of Dalian Ends 费用流找最短路

Our Journey of Dalian Ends

题意

给一个无向图,有边权,每个点用地名字符串表示。现在要从大连出发到达西安,并且必须经过上海,且给个点只能经过一次,问最短路径。

建图&思路

  1. 可以认为是找两条路径,起点都是上海,分别到达西安和大连,且经过的点不能重复,求路径和的最小长度。
  2. 将每个点拆点,拆分为入点和出点,入点向出点连一条边,容量为$1$,费用为$0$,代表这个点只能经过一次。
  3. 对于原图上的点,从一个城市的出点连一条边,到另一个城市所代表的点的入点。容量为$1$,费用为这条边的边权。反过来也需要连一条边,代表双向可行。
  4. 从源点向上海的出点连一条边,容量为$2$,费用为$0$,代表需要找到两条路径。
  5. 从西安和大连的出点,分别引一条边到汇点,容量为$1$,费用为$0$,代表只能是以这两个点为终点。
  6. 跑费用流,如果流量为2,那么费用就是两条路径的最短长度。
  7. 当然,如果输入数据中没有这三个城市,直接不行啊!

代码

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注