POJ2135 Farm Tour
riteme.site

[POJ2135] Farm Tour

原题题意

FJ老爷爷带着他的朋友到他的开心农场装B。FJ的农场是一张有$n(n\le1000)$个点,$m(m\le10000)$条边的无向图,每个点从$1$开始编号,每条边有一个边权。现在他想从$1$走到$n$,然后又从$n$走到$1$,他希望走的路最短每条路不走两遍

做法

看到要使走的路最短,就肯定要动用最短路了。然而他还需要两条,且这两条路径的每一条边都不同,用单纯的最短路难以办到。
不妨运用最大流的思想,将每条边拆成两个有向管道,且容量为1。那么,在增广时,只要是走过的边就会没有流量了,保证只有一条路径经过。
将最短路和最大流结合起来,就是最小费用最大流,这里我们将流网络的每条弧增加一个属性cost表示费用(注意不是单位费用),对应的就是原图中的边权。每次增广时选取费用最小的来进行增广,就能确保找到的增广路是原图中的最短路。
最后一个问题就是要找两条,这个其实很好办。我们利用源点和汇点来控制。首先建立一个源点,与$1$相连,容量为2,当然费用为0,这样不会最短路的结果。同样的方法,将汇点与$n$连接。这样,每次只能增广1的流,就能确保最多只有2条增广路。
需注意的是,在残留网络中,方向边的边权要为-cost,这样才能让增广正常进行。因此,Dijkstra算法并不适合。