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$ 连边即可。

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

Your browser is out-of-date!

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

×