【题意】：给你一个n*m的矩阵，对于矩阵中每个格子你可以选择放金蛋、银蛋或者不放。对于每个格子，不同选择会得到不同分数，但是如果相邻的格子放了相同的蛋就要扣一定的分数。问：最后能够得到最大的分数是多少？
【题解】：这题有点类似于方格取数。我们的思路是，一开始所有格子都放上金银蛋，然后去掉一些蛋使得布局合法，并且使我们去掉的价值尽可能小。对于这个问题，我们可以用最小割来求解，加入一个源点s和一个汇点t。我们把“在位置(i, j)放金蛋”看作一个点，记为G(i, j)，“在位置(i, j)放银蛋”看作一个点，记为S(i, j)，然后对格子黑白染色。
1、如果是白色格子，那么s -> G(i, j)，容量 = a[i][j]，G(i, j) -> S(i, j)，容量 = inf，S(i, j) -> t，容量 = b[i][j]。于是在求割集的时候，要么会拿掉金蛋（当然也就也拿掉了a[i][j]的价值），要么会拿掉银蛋，这就保证了这个格子里面至多只有一个金蛋或者一个银蛋（当然也可能金银蛋都没有——这时候S(i, j)，G(i, j)同时存在于割集）。
2、如果是黑色格子，那么s -> S(i, j)，容量 = b[i][j]，S(i, j) -> G(i, j)，容量 = inf，G(i, j) -> t，容量 = a[i][j]。原因同上。
3、对于白色格子，我们将G(i, j)（记为G1）与其周围的G(i, j)（任取一个记为G2）连一条边，容量 = g；将S(i, j)与其周围的S(i, j)连一条边，容量 = s。于是要么我们不会让金蛋 / 银蛋相邻，要么就会在最小割里面记录下来相邻带来的损失（以相邻的金蛋为例，因为有一条s -> G1 -> G2 -> t的边，所以要么把G1 / G2的价值割掉，要么就把金蛋相邻的损失割掉）。
所以其实每组割都和一个可行的去掉蛋的布局的做法一一对应，所以最小割就是去掉的最小价值。
于是，最终解 = 所有的a[i][j] + 所有的b[i][j] - 最小割。
最小割可以转化为最大流求解。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 5005
6 #define maxm 500005
7 #define MAX 55
8 const int INF = 1 << 30;
9 int eh[maxn], pre[maxn], cur[maxn], dist[maxn], cnt[maxn], low[maxn], tot;
10 int n, m, s, t, r, c, sum;
11 int color[MAX][MAX];
12 int dx[] = {0, 0, -1, 1};
13 int dy[] = {1, -1, 0, 0};
14
15 struct Edge {
16 int u, v, cap, flow, next;
17 }et[maxm];
18
19 void init() {
20 for(int i = 1; i < MAX; i++) {
21 bool flag = i & 1;
22 for(int j = 1; j < MAX; j++, flag = !flag)
23 color[i][j] = flag;
24 }
25 }
26
27 void isap_init() {
28 tot = sum = 0;
29 memset(eh, -1, sizeof(eh));
30 }
31
32 void add(int u, int v, int cap, int flow) {
33 Edge E = {u, v, cap, flow, eh[u]};
34 et[tot] = E;
35 eh[u] = tot++;
36 }
37
38 void addedge(int u, int v, int cap) {
39 add(u, v, cap, 0), add(v, u, 0, 0);
40 }
41
42 int isap(int s, int t, int n) {
43 int u, v, now, flow = 0;
44 memset(low, 0, sizeof(low));
45 memset(dist, 0, sizeof(dist));
46 memset(cnt, 0, sizeof(cnt));
47 low[s] = INF, cnt[0] = n;
48 u = s;
49 while(dist[s] < n) {
50 for(now = cur[u]; now != -1; now = et[now].next)
51 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
52 if(now != -1) {
53 cur[u] = pre[v] = now;
54 low[v] = min(low[u], et[now].cap - et[now].flow);
55 u = v;
56 if(u == t) {
57 for(; u != s; u = et[pre[u]].u) {
58 et[pre[u]].flow += low[t];
59 et[pre[u]^1].flow -= low[t];
60 }
61 low[s] = INF, flow += low[t];
62 }
63 } else {
64 if(--cnt[dist[u]] == 0) break;
65 dist[u] = n;
66 cur[u] = eh[u];
67 for(now = eh[u]; now != -1; now = et[now].next)
68 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
69 dist[u] = dist[et[now].v] + 1;
70 cnt[dist[u]]++;
71 if(u != s) u = et[pre[u]].u;
72 }
73 }
74 return flow;
75 }
76
77 int pos1(int i, int j) {
78 return (i - 1) * c + j;
79 }
80
81 int pos2(int i, int j) {
82 return r * c + (i - 1) * c + j;
83 }
84
85 int main() {
86 int tn, gval, sval, tt = 1, gold[MAX][MAX], silver[MAX][MAX];
87 scanf("%d", &tn);
88 init();
89 while(tt <= tn) {
90 isap_init();
91 scanf("%d%d%d%d", &r, &c, &gval, &sval);
92 for(int i = 1; i <= r; i++)
93 for(int j = 1; j <= c; j++)
94 scanf("%d", &gold[i][j]);
95 for(int i = 1; i <= r; i++)
96 for(int j = 1; j <= c; j++)
97 scanf("%d", &silver[i][j]);
98 s = 0, t = r * c * 2 + 1;
99 for(int i = 1; i <= r; i++) {
100 for(int j = 1; j <= c; j++) {
101 sum += gold[i][j] + silver[i][j];
102 if(color[i][j]) {
103 addedge(s, pos1(i, j), gold[i][j]);
104 addedge(pos1(i, j), pos2(i, j), INF);
105 addedge(pos2(i, j), t, silver[i][j]);
106 for(int k = 0; k < 4; k++) {
107 int x = i + dx[k], y = j + dy[k];
108 if(x >= 1 && x <= r && y >= 1 && y <= c) {
109 addedge(pos1(i, j), pos1(x, y), gval);
110 addedge(pos2(x, y), pos2(i, j), sval);
111 }
112 }
113 }
114 else {
115 addedge(s, pos2(i, j), silver[i][j]);
116 addedge(pos2(i, j), pos1(i, j), INF);
117 addedge(pos1(i, j), t, gold[i][j]);
118 }
119 }
120 }
121 printf("Case %d: %d\n", tt++, sum - isap(s, t, t - s + 1));
122 }
123 return 0;
124 }