1. 题目

传送门= ̄ω ̄=

2. 题解

这个题是一个很经典的问题:最大点权问题

二分图最大点权独立集问题,就是找出图中一些点,使得这些点之间没有边相连,这些点的权值之和最大。

独立集与覆盖集是互补的,求最大点权独立集可以转化为求最小点权覆盖集(最小点权支配集)。最小点权覆盖集问题可以转化为最小割问题解决。

结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。

(以上摘自http://blog.csdn.net/kevin66654/article/details/52540081

相关论文:https://wenku.baidu.com/view/986baf00b52acfc789ebc9a9.html

论文末尾有对这个问题的具体解释。

具体做法:
首先黑白染色,黑色四周四个格子是白色,白色四周四个格子是黑色。

接着从源点各连一条边到每个黑色格子上,容量为该黑色格子中的数字。

然后所有的白点各连一条边到汇点,容量为该白色格子中的数字。

最后,从每个黑色格子向与它相邻的四个白色格子(边缘上的格子没有四个)连一条容量无限大的边。

跑最大流得到最大流量为maxflow。

然后拿所有格子中的数字之和减去这个maxflow就是答案了。

代码: