HDUOJ 2732 - Leapin' Lizards

题面

你和一群蜥蜴进入了一个奇♂异的 n×mn \times m 迷宫里。当你在搜刮财宝的时候,某智障蜥蜴一不小心触发了机关,然后地板就消失了,于是你的每一只蜥蜴都站在了不同的石柱上。蜥蜴每次只能向东、西、南、北四个方向跳跃,且最大跳跃距离不超过 dd。每一个石柱都有一定的耐久度 wiw_i,每当蜥蜴跳离石柱时石柱的耐久度都会减少一个单位,而当耐久度变成 00 时石柱就会崩塌。在同一时刻上一个石柱上只能站一只蜥蜴。

请问至少有几只蜥蜴会陷入绝境。

数据范围

1n,m201 \le n, m \le 20

1d,wi31 \le d, w_i \le 3

题目链接

分析

建图

考虑网络流,我们先讨论如何建图。

不妨把每一个石柱看成一个点,而石柱的耐久度不妨看作这个点的“点权”。

既然要限制每一个点的访问次数,那么我们考虑拆点

我们将每个石柱 ii 拆成两个点:i1i_1i2i_2,并且在 i1i_1i2i_2 间连上一条权值为该石柱耐久度 wiw_i 的边。我们规定流只能从 i1i_1 流入,并只能从 i2i_2 流出,这样就等价于限制了流经该点流量的大小。

接下来的部分就很简单了:

  • 如果蜥蜴可以从石柱 ii 跳跃至石柱 jj,那么我们将 i2i_2j1j_1 相连,边权设为 ++\infty(这条边的作用仅仅是引流,因此无需限制流量)。
  • 如果石柱 ii 在初始时有蜥蜴,则将源点与 i1i_1 相连,边权设为 11 (因为只有一只蜥蜴)。
  • 如果石柱 ii 距离边界的距离小于 dd,则将 i2i_2 与汇点相连,边权设为 ++\infty(同理,点权已经限制过了,作用仅为引流)。

优化

我们不妨引入一点贪心的思想。既然要让尽可能多的蜥蜴逃离迷宫,那么每只蜥蜴经过的石柱应当尽可能少。因此,一旦蜥蜴来到了距离边界小于 dd 的某石柱 ii,这时它应当直接选择跳出迷宫,而不是在迷宫里面接着乱逛。

因此,对于距离边界小于 dd 的石柱 ii,我们不必将其与任何其它与之距离在 dd 以内的石柱相连。既然石柱 ii 只能到汇点,我们也可以不必对其拆点了。我们可以直接将 i1i_1 与汇点相连,边权设为该石柱的耐久度 wiw_i (这样就可以限制点权了)。

实现

参考代码采用了 Dinic 算法来求解最大流。

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/03/27/hduoj-2732/