给你一个m*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。

最大点权独立集,应用最小割求解

构图:

增加源点s和汇点t.每个格子作为一个点,进行黑白染色(相邻的一黑一白).

源点到所有黑点引一条权为黑点点权的边.所有白点到汇点引一条权为白点点权的边.

每个黑点到与其相邻的白点引一条权为无穷的边.

结果:所有点权之和减去最小割容量(即最大流流量).

分析:

因为最大流不是无穷的,所以最小割中不会包含(黑点到白点的)无穷边.所以任意不包含无穷边的割都是一种选择方案.为什么必须是割呢?因为若割中的每一条边对应这一个不选取的点,则去掉这些点之后,原图中便不存在s--u--v--t的路的,即选择的点中没有相邻的u和v了.自然当割为最小割时,剩下的点的权和最大,为所求结果.

大概就是这样子了吧,不知道有没有理解错......