前言:刚学了网络流 G 就有了,大涨!
根据题意,我们可以提取出核心的两个对立方:'+' 和 '-',一个 '+' 消失代价为 111,一个 '-' 消失收益为 111。
考虑一次操作影响:是强制地将左,右,下非 '#' 修改为 '#',这时候就出现了依赖关系:选择 uuu 就必须选择 vvv,可以在 uuu 和 vvv 中连边,这样就形成了一个图,我们要在满足依赖关系的条件下,选择一个子集,是的收益与代价的差最大。显然是一个最小割。
建立一个源点 SSS 连向所有收益点,汇点 TTT 连向所有代价点,容量为 111。
对于每个非 '#' 的格子,与左,右,下非 '#' 的点连一条容量为 +∞+\infty+∞。
这是为了满足强制关系,不让这两个点分到不同的集合(因为如果分到不同集合,显然不可能作为最小割)。
最后处理一下初始值跑一个 Dinic 即可。