题意
一个 \(n\times m\) 的区域内,有以下 \(5\) 种地形:
-
~
:无法通行。 -
.
:只能通行 \(1\) 次。 -
@
:可以通行 \(+\infty\) 次。 -
*
:初始有一个人的.
。 -
#
:安全位置,可以通行 \(+\infty\) 次,但至多能容纳 \(p\) 个人。
人每次可以走到相邻的位置,问最多有多少个人可以抵达安全位置。
思路
网络流,因为有通行限制,我们把每个点拆成入点和出点,对于 ~
入点与出点之间的边流量为 \(0\),.
和 *
流量为 \(1\),#
和 @
为 \(+\infty\),每个位置的出点向相邻的入点连边,流量为 \(+\infty\),源点向所有 *
的入点连一条流量为 \(1\) 的边,所有 #
的出点向汇点连一条流量为 \(p\) 的边。跑一次最大流就完了。****