poj2135

时间:2024-01-12 09:50:44

加深对最小费用最大流的理解题

题目求无向图来回和最短的路径,每条边只能走一次

不难想到,无向图中来回等于从源点出发走两条不同路径到汇点(区别于k短路,这里每条边只能走一次);

考虑到边的限制,不难想到,把限制变成容量

连超级源点到起点,容量为2,费用为0;

最小费用最大流即可

这里就不贴代码,以前用的数组模拟邻接表实在太丑陋了

这里想说的是,其实最短路径可以看做特殊的最小费用最大流,每条边容量看做1即可