tkdsheep-solution-0061

从 Trac 迁移的文章

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

原文章内容如下：

{{{
又是可爱的格子题，背景取自塔防游戏《防御阵型：觉醒》

在m*n的格子上，有些格子你可以建一种特定的炮塔，有些格子不能造
每种炮塔的攻击力都是1，区别就是攻击的范围不同

然后凡是没有造炮塔的格子都会出现怪物
每个格子的怪物数量可能不同，需要对怪物造成的伤害值也就不同，这个题目输入会给出

现在就问能不能合理安排炮塔的攻击区域，把所有怪物都消灭

现在先分析一下每种炮塔的特点

Twin Tower：攻击周围8个格子中的2个，一旦选定这两个格子，就不能攻击剩下6个格子了
Cannon Tower： 首先从上下左右四个方向中选一个方向，然后可以攻击这个方向上的任意一个格子，但是选定格子之后就不能攻击这个方向上的其他格子了
Missile Tower： 攻击地图上的任意一个格子，并且攻击了一个格子就不能攻击其他格子了
Laser Tower: 范围攻击塔，跟Canno Tower类似，但是可以【同时】攻击一个方向上的所有格子
Fire Tower： 跟Laser Tower类似的范围攻击塔，但攻击的是十字区域，有两种方向可选，具体见题目描述
Magnetic Bomb： 地雷，只能攻击自身所在格子，并且不能算作炮塔，所以这个格子依然会有怪物出现

这很明显是一个网络流模型，建一个超源点，与所有炮塔相连，然后所有怪物格子与超汇点相连，容量为这个格子需要的伤害
炮塔与能攻击到的格子相连，比如Twin Tower，它可以攻击2个格子，那么源点与它连一条容量为2的边，Twin Tower与它能攻击到的8个格子均连边，容量为1

但这里有个问题，就是Laser Tower和Fire Tower怎么建图？由于他们有多种方向可选，并且又是范围攻击，所以是无法建网络流的边的，如果强行建边，也无法控制流量的分配
可能会导致代表伤害的流量被分流到两个方向上，自己画图看看就知道了

而注意到题目有一个加粗条件，每种塔的数量不超过5，所以可以先对这两种塔dfs一下，然后再对剩下的塔做网络流看是否满流即可

}}}

又是可爱的格子题，背景取自塔防游戏《防御阵型：觉醒》
在m*n的格子上，有些格子你可以建一种特定的炮塔，有些格子不能造
每种炮塔的攻击力都是1，区别就是攻击的范围不同
然后凡是没有造炮塔的格子都会出现怪物
每个格子的怪物数量可能不同，需要对怪物造成的伤害值也就不同，这个题目输入会给出
现在就问能不能合理安排炮塔的攻击区域，把所有怪物都消灭
现在先分析一下每种炮塔的特点
Twin Tower：攻击周围8个格子中的2个，一旦选定这两个格子，就不能攻击剩下6个格子了
Cannon Tower： 首先从上下左右四个方向中选一个方向，然后可以攻击这个方向上的任意一个格子，但是选定格子之后就不能攻击这个方向上的其他格子了
Missile Tower： 攻击地图上的任意一个格子，并且攻击了一个格子就不能攻击其他格子了
Laser Tower: 范围攻击塔，跟Canno Tower类似，但是可以【同时】攻击一个方向上的所有格子
Fire Tower： 跟Laser Tower类似的范围攻击塔，但攻击的是十字区域，有两种方向可选，具体见题目描述
Magnetic Bomb： 地雷，只能攻击自身所在格子，并且不能算作炮塔，所以这个格子依然会有怪物出现
这很明显是一个网络流模型，建一个超源点，与所有炮塔相连，然后所有怪物格子与超汇点相连，容量为这个格子需要的伤害
炮塔与能攻击到的格子相连，比如Twin Tower，它可以攻击2个格子，那么源点与它连一条容量为2的边，Twin Tower与它能攻击到的8个格子均连边，容量为1
但这里有个问题，就是Laser Tower和Fire Tower怎么建图？由于他们有多种方向可选，并且又是范围攻击，所以是无法建网络流的边的，如果强行建边，也无法控制流量的分配
可能会导致代表伤害的流量被分流到两个方向上，自己画图看看就知道了
而注意到题目有一个加粗条件，每种塔的数量不超过5，所以可以先对这两种塔dfs一下，然后再对剩下的塔做网络流看是否满流即可