首先网络流证明就略过了，先说一下如何建模。

P2774

有一个 \(m\) 行 \(n\) 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

思路

首先发现，相邻的方格是互斥的，则把 \(i+j\) 为偶数的 \((i,j)\) 放左边，把 \(i+j\) 为奇数的 \((i,j)\) 放右边。

假设最开始把所有数全选，现在需要删去最少多少数。现在要想办法构造一个模型，它支持：

• 能删掉一个元素，表示不取这个方格；
• 删掉的代价为方格的权值；
• 要么删掉的总是保证策略最优的，要么能反悔；
• 最终状态为：没有互斥的方格了。

那么，直接连边，跑最小割即可。

• \(S\) 向 \(i+j\) 为偶数的 \((i,j)\) 连一条权值为 \(a_{i,j}\) 的边。
• \(i+j\) 为奇数的 \((i,j)\) 向 \(T\) 连一条权值为 \(a_{i,j}\) 的边。
• 对于相邻两个方格 \((i,j)\)，\((x,y)\)，连一条权值为 INF 的边。

考虑为什么是对的：

• 首先，如果不选当前方格，等价于把 \(S\) 向 \((i,j)\) 的边或 \((i,j)\) 向 \(T\) 的边割掉。
• 其次，因为中间的边是 INF，不会被删掉。所以想要不联通，只能割掉两边的边。