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 ,我还是太菜了。

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

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

最大流最小割模板题。

想当年第一次打开 BZOJ 做完 A + B 之后看得一脸懵逼的就是这道题,没想到现如今看起来这么简单

不过还是没有秒切,双向边没看到调了好久 QAQ

好了,关于那个连边。这是本人单向边网络流连边:

1
2
3
4
5
inline void add_edge(int u, int v, int w) {
nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, val[tot] = 0, hed[v] = tot++;
return;
}

这是本人的双向网络流连边(连两遍也是一样的):

1
2
3
4
5
inline void add_edge(int u, int v, int w) {
nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, val[tot] = w, hed[v] = tot++;
return;
}

另外 $最大流 = 最小割$ 不必多说了吧,贴个直观的证明(来自:https://jecvay.com/2014/11/what-is-min-cut.html):

1.最大流不可能大于最小割, 因为最大流所有的水流都一定经过最小割那些割边, 流过的水流怎么可能比水管容量还大呢?

2.最大流不可能小于最小割, 如果小, 那么说明水管容量没有物尽其用, 可以继续加大水流.

那么 SAP + 当前弧优化 + 断层优化 + 反向 BFS 一遍轻松跑过。

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

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

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

去他妈的NOI难度

从 $S$ 到 byx 的每个人连条容量为生命的边,从手气君的每个人到 $E$ 连条容量为生命的边;如果 byx 的这个人能打赢对方的某个人连一条容量为 $1$ 的边,$+1s$ 的话直接加到生命里,最后跑一遍最大流即可。

Your browser is out-of-date!

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

×