[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算法并不适合。