BZOJ2132 圈地计划

发表于

  题意:一个矩形区域，每个小区域可以建商业区或工业区，可以获得不同价值。对每个区域，如果相邻区域建的区不同，则该区域可以获得额外价值。求最大总价值。

  相邻区域相同则获得价值的建模，之前也提到过。只需要新建两个点用对应价值连向两种不同决策。如果对两种决策而言，同时选获得的价值一样，则可以直接将两区域互相连边即可。
  那么不同呢?我们发现这个图是一个矩阵，也就是一个二分图。我们将节点黑白染色放在两部，对白节点，源点为建商业区的决策，汇点为建工业区的决策。黑点正好相反。这样我们就巧妙地转化为区域相同的问题了。

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define erep(i, u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define ms(a, b) memset(a, b, sizeof a);
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c - '0'; isdigit(c = getchar()); (x *= 10) += c - '0');
    if(flag) x = -x; return x;
}
const int maxn = 10010, maxm = 60010, INF = 0x3f3f3f3f;
int n, m, sum;
int head[maxn], nxt[maxm << 1], to[maxm << 1], c[maxm << 1], e = 1;
void ae(int x, int y, int w) { to[++e] = y; nxt[e] = head[x]; head[x] = e; c[e] = w; }
namespace isap
{
	int S, T, N, gap[maxn], dis[maxn];
	int dfs(int u, int flow)
	{
		if(u == T) return flow;
		int res = flow;
		erep(i, u) if(c[i] && dis[u] == dis[v] + 1)
		{
			int d = dfs(v, min(c[i], res));
			c[i] -= d; c[i ^ 1] += d; res -= d;
			if(!res) return flow;
		}
		if(!--gap[dis[u]]) dis[S] = N;
		++gap[++dis[u]];
		return flow - res;
	}
	int maxflow(int s, int t, int tot)
	{
		S = s, T = t, N = tot; int flow = 0;
		ms(gap, 0); ms(dis, 0);
		for(gap[0] = N; dis[S] < N;) flow += dfs(S, INF);
		return flow;
	}
}
int a[110][110], b[110][110], w[110][110];
int d[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
bool in(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }
int main()
{
#ifndef ONLINE_JUDGE
	freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
	read(n); read(m); int t = n * m + 1;
	rep(i, 1, n) rep(j, 1, m) sum += read(a[i][j]);
	rep(i, 1, n) rep(j, 1, m) sum += read(b[i][j]);
	rep(i, 1, n) rep(j, 1, m) read(w[i][j]);
	rep(i, 1, n) rep(j, 1, m)
	{
		int id = (i - 1) * m + j;
		if((i & 1) ^ (j & 1))
		{
			ae(0, id, a[i][j]); ae(id, 0, 0);
			ae(id, t, b[i][j]); ae(t, id, 0);
			rep(k, 0, 3)
			{
				int x = i + d[k][0], y = j + d[k][1];
				if(in(x, y))
				{
					int idx = (x - 1) * m + y;
					ae(id, idx, w[i][j] + w[x][y]); ae(idx, id, 0);
					ae(idx, id, w[i][j] + w[x][y]); ae(id, idx, 0);
					sum += w[i][j] + w[x][y];
				}
			}
		}
		else
		{
			ae(0, id, b[i][j]); ae(id, 0, 0);
			ae(id, t, a[i][j]); ae(t, id, 0);
		}
	}
	printf("%d\n", sum - isap::maxflow(0, t, t + 1));
	return 0;
}