tkdsheep-ZOJ3362

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

做这题之前回想了一下，我好像从来没有写过费用流的题。。
这题很容易让人联想到费用流的模型，但是建图并不是那么简单直白，如果是最小费用最大流的话，题目并没有对"最大流"的要求，整个题目的要求只是总费用尽可能小（将运输费用设为正，啤酒卖出费用设为负）
如果直接套最小费用最大流的模板，就有可能出现这样的情况：为了使流最大，有一些流量产生的费用是正数，也就是说这部分流量是赔本的。。
于是这又是一道需要了解算法具体实现过程的题目，我们需要对模板进行修改，~~ZJU的费用流模板不够健壮，不能处理多重边的情况~~ 囧。。想了一下似乎不能这么说。。只能说是我看不懂@.@
我直接用了shi哥的模板，每次找增广路，如果这条增广路的费用是正数，就直接break不找了（因为每次都找的是费用最小的一条路来增广，这条路都赔本，那肯定没其他路可以找了)，这就是模板需要改动的地方，shi哥在代码里也写了注释的，仰慕shi哥
有了这题作基础，应该就可以做VKCUP Round3的那道费用流的题了

做这题之前回想了一下，我好像从来没有写过费用流的题。。

这题很容易让人联想到费用流的模型，但是建图并不是那么简单直白，如果是最小费用最大流的话，题目并没有对"最大流"的要求，整个题目的要求只是总费用尽可能小（将运输费用设为正，啤酒卖出费用设为负）

如果直接套最小费用最大流的模板，就有可能出现这样的情况：为了使流最大，有一些流量产生的费用是正数，也就是说这部分流量是赔本的。。

于是这又是一道需要了解算法具体实现过程的题目，我们需要对模板进行修改，ZJU的费用流模板不够健壮，不能处理多重边的情况 囧。。想了一下似乎不能这么说。。只能说是我看不懂@.@

我直接用了shi哥的模板，每次找增广路，如果这条增广路的费用是正数，就直接break不找了（因为每次都找的是费用最小的一条路来增广，这条路都赔本，那肯定没其他路可以找了)，这就是模板需要改动的地方，shi哥在代码里也写了注释的，仰慕shi哥

有了这题作基础，应该就可以做VKCUP Round3的那道费用流的题了