【题意】:给你一个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[] = {00-11};
 13 int dy[] = {1-100};
 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, -1sizeof(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, 00);
 40 }
 41 
 42 int isap(int s, int t, int n) {
 43     int u, v, now, flow = 0;
 44     memset(low, 0sizeof(low));
 45     memset(dist, 0sizeof(dist));
 46     memset(cnt, 0sizeof(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] + 1break;
 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]] == 0break;
 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 }