[国家集训队] 圈地计划

题目大意

给定一个 n×mn \times m 的网格,每个位置可选获得两种权值 ai,ja_{i, j}bi,jb_{i, j} ;同时,如果位置 (i,  j)(i, \; j) 的四周有 kk 个与它所选权值种类不同,将额外获得 k×ci,jk \times c_{i, j} 的权值。求可获得的最大权值。

1n,  m1001 \leqslant n, \; m \leqslant 100

1ai,j,  bi,j,  ci,j1,0001 \leqslant a_{i, j}, \; b_{i, j}, \; c_{i, j} \leqslant 1,000

题目链接

【国家集训队】圈地计划 - Luogu 1935

题解

最小割/最大权闭合图。

说实话,直到这道题,我才明白了为什么最大权闭合图的本质是求最小割。(我好菜啊.jpg)

先让相邻的点取不同的权值,对于 AA 类点,从源点向其连容量为 ai,ja_{i, j} 的边,向汇点连容量为 bi,jb_{i, j} 的边, BB 类点相反。同时相邻两点间连双向边,容量为两点 cc 值的和。用所有权值的和减去最小割,就是答案。

为什么呢?首先,我们得到的答案就是图中不加割边的权值和。考虑相邻两点,割断有两种情况,即都割开与汇(或源)点的边,或割开一条与汇点的边、一条与源点的边,以及它们中间的边。前者表示两点权值种类不同,还剩下权值 au+bv+cu+cva_u + b_v + c_u + c_v ;后者则是两点权值种类相同,还剩下权值 au+aua_u + a_u(或 bu+bvb_u + b_v )。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
const int MAXN = 105;
struct Edge;
struct Node {
Edge *e, *curr;
int level;
} N[MAXN * MAXN];
struct Edge {
Node *u, *v;
Edge *next, *rev;
int cap, flow;
Edge(Node *u, Node *v, int cap) : u(u), v(v), next(u->e), cap(cap), flow(0) {}
};
void addEdge(int u, int v, int cap, bool bi = false) {
N[u].e = new Edge(&N[u], &N[v], cap);
N[v].e = new Edge(&N[v], &N[u], bi ? cap : 0);
N[u].e->rev = N[v].e;
N[v].e->rev = N[u].e;
}
namespace Dinic {
bool makeLevelGraph(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) N[i].level = 0;
std::queue<Node *> q;
q.push(s);
s->level = 1;
while (!q.empty()) {
Node *u = q.front();
q.pop();
for (Edge *e = u->e; e; e = e->next) {
if (e->cap > e->flow && e->v->level == 0) {
e->v->level = u->level + 1;
if (e->v == t) return true;
else q.push(e->v);
}
}
}
return false;
}
int findPath(Node *s, Node *t, int limit = INT_MAX) {
if (s == t) return limit;
for (Edge *&e = s->curr; e; e = e->next) {
if (e->cap > e->flow && e->v->level == s->level + 1) {
int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
if (flow > 0) {
e->flow += flow;
e->rev->flow -= flow;
return flow;
}
}
}
return 0;
}
int solve(int s, int t, int n) {
int res = 0;
while (makeLevelGraph(&N[s], &N[t], n)) {
for (int i = 0; i < n; i++) N[i].curr = N[i].e;
int flow;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}
return res;
}
}
int n, m;
int getID(int x, int y) {
return (x - 1) * m + y;
}
int main() {
scanf("%d %d", &n, &m);
const int s = 0, t = n * m + 1;
int tot = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
int w;
scanf("%d", &w);
tot += w;
if ((i + j) % 2 == 0) addEdge(s, getID(i, j), w);
else addEdge(getID(i, j), t, w);
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
int w;
scanf("%d", &w);
tot += w;
if ((i + j) % 2 == 1) addEdge(s, getID(i, j), w);
else addEdge(getID(i, j), t, w);
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
int w;
scanf("%d", &w);
if (i != 1) addEdge(getID(i, j), getID(i - 1, j), w, true), tot += w;
if (i != n) addEdge(getID(i, j), getID(i + 1, j), w, true), tot += w;
if (j != 1) addEdge(getID(i, j), getID(i, j - 1), w, true), tot += w;
if (j != m) addEdge(getID(i, j), getID(i, j + 1), w, true), tot += w;
}
int maxFlow = Dinic::solve(s, t, t + 1);
printf("%d\n", tot - maxFlow);
return 0;
}