网络流裸题,没什么好说的。
需要注意的是,我们在给厨师拆点的时候,如果先把边都连好,时间是会炸掉的。所以我们就没“用掉”一个厨师新建一次点即可。

BZOJ5403 - marshland

这个数据范围容易让人想到网络流,问题在于这个网络流怎么流?

首先可以发现,如果我们要放石头,一定只会放在 $x + y$ 为奇数的格子,否则放了不如不放。所以把这些点拆点,连一条费用为 $a[x][y]$ ,流量为 $1$ 的边。

接下来,我们可以构造一种对 $x + y$ 为偶数的格子的黑白染色方案,使得一个 L 型石头的两个 $x + y$ 为偶数的格子异色。容易发现,我们只需要对所有 $x$ 和 $y$ 都是奇数的格子染黑, $x$ 和 $y$ 都是偶数的格子染白。同理,拆成两个点,中间连一条费用为 $0$ ,流量为 $1$ 的边。

同时,为了使得总放置的石头数为 $m$ ,我们还需要再建一个点 $P$ 。

于是源点 $S$ 向 $P$ 连边, $P$ 向黑点连边,黑点向 $x + y$ 为奇数的点连边, $x + y$ 为奇数的点向白点连边,白点向汇点 $E$ 连边即可。

需要注意的是,我们跑最大费用最大流,但是我们只需要费用最大,而不是流量。由于我们采用增广路算法,每次新增的流量的花费一定递减,所以当花费是负数时直接跳出即可。

BZOJ1070 - [SCOI2007]修车

最小费用最大流。由于一个工人在给一个顾客服务后还能再给一个顾客服务, 所以把每个顾客和每个工人建点显然不能完成任务。

那么我们考虑把第 $i$ 个工人建成 $n$ 个点,表示为 $P(i,j) (i \in [1, m], j \in [1, n])$。把第 $i$ 个顾客表示为 $T(k)$。

把 $T(k)$ 依次向 $P(i,j)$ 连边,流量为 $1$ ,费用为 $w(k,i) \times j$ 。表示第 $k$ 个顾客被第 $i$ 个工人倒数第 $j$ 个服务对答案产生的贡献(即包括在它之后的人的等待时间,而不是这个人自己的花费)。

最后从源点向每个顾客连流量 $1$ ,费用 $0$ 的边,$n \times m$ 个工人向汇点连流量 $1$ ,费用为 $0$ 的边,跑最小费用最大流即可。

到这题为止网络流 24 题也快刷完了呢,还剩下几道码量特大的等着以后有空去浪费时间(逃

这题一眼最小费用最大流,一开始我想了个类似于 NOI2008 志愿者招募 之类的利用满流的方法,但是一直没有调出来。后来怂了,直接连边,最后因为有个 - 1 没有删干净还是调了老半天。orz ,我还是太菜了。

把每一天分成两个节点,一个接受干净的毛巾,一个输出用过的毛巾。直接在这两个点之间连边显然不现实,我们可以分别把这两个点和源点、汇点连边。然后再按照题目条件一一连上对应边。这样最大流肯定能够跑满,求最小费用的话就是这图的最小费用最大流了。

这告诉我们对于不清楚的知识点不要瞎用。

巧妙的使用满流的特性解决问题。

对每一天,连一条容量为 $INF - 需求人数$ 的边,对于补充的人连一条容量为 $INF$ ,花费为价格的边。

对这个图跑最小费用最大流,其中最大流一定是 $INF$ ,最小费用即答案。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×