BZOJ2127 happiness

发表于

  题意:文理分科，全班每个同学分到文科或理科有不同的喜悦值。相邻两个同学同时分到文科和理科有额外喜悦值。求分配方案使总喜悦值最大。

  这道题是比较经典的最小割模型了。
  源点文，汇点理，将每个同学与对应点连对应喜悦值的边。处理相邻就新建点，向对应文或理科点连对应喜悦值的边，向两个人连INF。最小割即为答案。
  不过这道题调了比较长的时间。最后发现时建点时编号过于”精打细算”，将点数与实际编到的号数混淆导致弄错了。以后建点与边的时候一定要算准，而且在条件允许的情况下开得宽松一些，才可以防止难以调试的错误发生。

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#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 = 50010, maxm = 140010, INF = 0x3f3f3f3f;
int n, m, tot;
int a[110][110], b[110][110], samed_a[110][110], samed_b[110][110], samer_a[110][110], samer_b[110][110];
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 dinic
{
	int S, T, dis[maxn], cur[maxn];
	bool bfs()
	{
		queue<int> q; ms(dis, 0);
		q.push(S); dis[S] = 1;
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			erep(i, u) if(c[i] && !dis[v]) dis[v] = dis[u] + 1, q.push(v);
		}
		return dis[T];
	}
	int dfs(int u, int flow)
	{
		if(u == T) return flow;
		int res = flow;
		for(int& i = cur[u]; i; i = nxt[i])
		{
			int v = to[i];
			if(c[i] && dis[u] + 1 == dis[v])
			{
				int d = dfs(v, min(c[i], res));
				c[i] -= d; c[i ^ 1] += d;
				res -= d; if(!res) return flow;
			}
		}
		return flow - res;
	}
	int maxflow(int s, int t)
	{
		S = s, T = t; int flow = 0;
		while(bfs())
		{
			memcpy(cur, head, sizeof head);
			flow += dfs(S, INF);
		}
		return flow;
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
	read(n); read(m); int t = 5 * n * m + 1;
	rep(i, 1, n) rep(j, 1, m) tot += read(a[i][j]);
	rep(i, 1, n) rep(j, 1, m) tot += read(b[i][j]);
	rep(i, 1, n - 1) rep(j, 1, m) tot += read(samed_a[i][j]);
	rep(i, 1, n - 1) rep(j, 1, m) tot += read(samed_b[i][j]);
	rep(i, 1, n) rep(j, 1, m - 1) tot += read(samer_a[i][j]);
	rep(i, 1, n) rep(j, 1, m - 1) tot += read(samer_b[i][j]);
	rep(i, 1, n) rep(j, 1, m)
	{
		int id = (i - 1) * m + j;
		ae(0, id, a[i][j]), ae(id, 0, 0);
		ae(id, t, b[i][j]), ae(t, id, 0);
		if(i != n)
		{
			int idx = n * m + id;
			ae(0, idx, samed_a[i][j]), ae(idx, 0, 0);
			ae(idx, id, INF), ae(id, idx, 0);
			ae(idx, id + m, INF), ae(id + m, idx, 0);
			idx = 2 * n * m + id;
			ae(id, idx, INF), ae(idx, id, 0);
			ae(id + m, idx, INF), ae(idx, id + m, 0);
			ae(idx, t, samed_b[i][j]), ae(t, idx, 0);
		}
		if(j != m)
		{
			int idx = 3 * n * m + id;
			ae(0, idx, samer_a[i][j]), ae(idx, 0, 0);
			ae(idx, id, INF), ae(id, idx, 0);
			ae(idx, id + 1, INF), ae(id + 1, idx, 0);
			idx = 4 * n * m + id;
			ae(id, idx, INF), ae(idx, id, 0);
			ae(id + 1, idx, INF), ae(idx, id + 1, 0);
			ae(idx, t, samer_b[i][j]), ae(t, idx, 0);
		}
	}
	printf("%d\n", tot - dinic::maxflow(0, t));
	return 0;
}