题解 P2774 【方格取数问题】
学委
2018-12-28 08:38:38
限制条件是——如果要取某一个方格，那么禁止取相邻的**四个**方格，不限制**其它所有**方格。
所以猜测，从禁止的角度考虑才会更高效。也就是说，先选中所有方格，再想办法删去**权值和**尽量小的一批方格。
___
相邻的概念是，横坐标或纵坐标中的一个相差 $1$，所以两点的横纵坐标之和**奇偶性不同**。
于是，横纵坐标和的奇偶性相同的两个点肯定不互斥（奇偶性不同的**可能**互斥）。把互斥的点连边的话，会形成一个二分图。
但先不管这个。
要想办法构造一个模型，它：
* **能删掉一个元素，表示不取这个方格；**
* **删掉的代价为方格的权值；**
* **要么删掉的总是保证策略最优的，要么能反悔；**
* **最终状态为：没有互斥的方格了。**
好像能发现对应的模型了，大概是**图**一类的东西：
* 删掉连向方格的边
* 边权为方格的权值
* 网络流搞一搞
* **割**
___
怎么构造一个合适的图呢？最好能利用上面的二分图。并不容易想到：
源点连向二分图的一个点集（横纵坐标之和为奇数的那些方格），边权为点权。**删一条边表示不取这个方格。**
二分图的另一个点集连向超级汇，边权还是点权。删边也表示不取此点。
二分图内部的边，连接着互斥的点。边权全部赋为 $inf$，以保证在最小割中不被删。啥意思？
想象一下通过某种方式，求出了该图最小割。
* 因为是最小割，所以中间的 $inf$ 边没删，删掉的都是源点连出的边，或连入汇点的边。
**因此这个割能够确切表示：不取某些方格。**（删掉中间边本来就没有意义，不能表示对方格的操作；只有两侧的边具有意义）
* 因为是割，所以图不连通。**不连通**，就已经保证没有取到任何互斥的方格（假设图中还有互斥方格，也就是两者在图中各自所属的边还没删，再因为它们中间的 $inf$ 边也没删，所以图还是连通的）
最后只需知道**最大流 = 最小割**就好了。
```cpp
//Dinic 理解代价低
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#define N 10010
#define E 100010
#define S 0
#define T (m * n + 1)
#define code(i, j) ((i - 1) * m + j)//点的线性标号
#define between(x, flo, top) (flo <= x and x <= top)//您是不是不喜欢这个qwq
int getint() {
int res = 0, ch = getchar();
while (!isdigit(ch) and ch != EOF)
ch = getchar();
while (isdigit(ch))
res = res * 10 + (ch - '0'), ch = getchar();
return res;
}
inline int min(int x, int y) { return (x < y) ? x : y; }
using std::queue;
const int d[4][2] = {//待会枚举四个方向用的
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
int m, n;
int sum = 0;
int first[N];
int nxt[E], to[E], val[E], cnt = 1;
void addE(int u, int v, int w) {
++cnt;
to[cnt] = v;
val[cnt] = w;
nxt[cnt] = first[u];
first[u] = cnt;
}
int dep[N];
queue<int> q;
bool bfs() {
memset(dep, 0, sizeof(dep));
dep[S] = 1;
q.push(S);
while (not q.empty()) {
int u = q.front();
q.pop();
for (int p = first[u]; p; p = nxt[p]) {
int v = to[p];
if (dep[v])
continue;
if (val[p]) {//放心，开始都是正权的情况下，不会出现负数的
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[T];
}
int dfs(int u, int in) {
if (u == T)
return in;
int out = 0;
for (int p = first[u]; p and in; p = nxt[p]) {
if (val[p] == 0)
continue;
int v = to[p];
if (dep[v] != dep[u] + 1)
continue;
int res = dfs(v, min(val[p], in));
val[p] -= res;
val[p ^ 1] += res;
in -= res;
out += res;
}
return out;
}
int main() {
n = getint(), m = getint();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
int w = 0;
sum += w = getint();//假定全部都取，随后会删
if ((i + j) % 2 == 0) {//阵营A，源点连向自己，自己连向阵营B
addE(S, code(i, j), w);
addE(code(i, j), S, 0);
for (int k = 0; k <= 3; ++k) {
int x = i + d[k][0], y = j + d[k][1];
if (between(x, 1, n) and between(y, 1, m)) {
addE(code(i, j), code(x, y), 2e9);
addE(code(x, y), code(i, j), 0);
}
}
}
else {//阵营B，连向汇点
addE(code(i, j), T, w);
addE(T, code(i, j), 0);
}
}
int cut = 0;//最小割
while (bfs())
cut += dfs(S, 2e9);//最小割 = 最大流
printf("%d\n", sum - cut);
return 0;
}
```