【最小割】happiness

网络流

传送门：BZOJ2127

思路：考虑相邻两个学生的情况，

先假设喜悦值最大，然后把收获的喜悦值作为容量建模，切断表示不选的代价，

然后跑最小割，喜悦值总和减去最小割即可。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 100000000
int ans,n,m,s,t,tot,x,level[30000],iter[30000],head[30000],q[300000];
struct edge{int v,cap,rev,nxt;}E[8000000];
void add(int x,int y,int k){
	E[++tot].v=y; E[tot].cap=k; E[tot].rev=tot+1; E[tot].nxt=head[x]; head[x]=tot;
	E[++tot].v=x; E[tot].cap=0; E[tot].rev=tot-1; E[tot].nxt=head[y]; head[y]=tot;
}
	
void bfs(int s){
	memset(level,-1,sizeof level);
	level[s]=0;
	int tt=0,ww=1;
	q[1]=s;
	while (tt<ww){
		tt++;
		int v=q[tt];
		for (int i=head[v];i;i=E[i].nxt){
			edge &e=E[i];
			if (e.cap>0 && level[e.v]<0){
				level[e.v]=level[v]+1;
				q[++ww]=e.v;
			}
		}
	}
}
int dfs(int v,int t,int f){
	if (v==t) return f;
	for (int &i=iter[v];i;i=E[i].nxt){
		edge &e=E[i];
		if (e.cap>0 && level[v]<level[e.v]){
			int d=dfs(e.v,t,min(f,e.cap));
			if (d>0){
				e.cap-=d;
				E[e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
int dinic(int s,int t){
	int flow=0;
	for (;;){
		bfs(s);
		if (level[t]<0) break;
		for (int i=1;i<=n*m+2;i++) iter[i]=head[i];
		int f=0;
		while ((f=dfs(s,t,INF))>0)
			flow+=f;
	}
	return flow;
}
int main(){
	scanf("%d%d",&n,&m);
	s=n*m+1; t=n*m+2;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			scanf("%d",&x);
			add(s,(i-1)*m+j,x*2);
			ans+=x*2;
		}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			scanf("%d",&x);
			add((i-1)*m+j,t,x*2);
			ans+=x*2;
		}
	for (int i=1;i<n;i++)
		for (int j=1;j<=m;j++){
			scanf("%d",&x);
			add(s,(i-1)*m+j,x);
			add(s,i*m+j,x);
			add((i-1)*m+j,i*m+j,x);
			add(i*m+j,(i-1)*m+j,x);
			ans+=x*2;
		}
	for (int i=1;i<n;i++)
		for (int j=1;j<=m;j++){
			scanf("%d",&x);
			add((i-1)*m+j,t,x);
			add(i*m+j,t,x);
			add((i-1)*m+j,i*m+j,x);
			add(i*m+j,(i-1)*m+j,x);
			ans+=x*2;
		}
	for (int i=1;i<=n;i++)
		for (int j=1;j<m;j++){
			scanf("%d",&x);
			add(s,(i-1)*m+j,x);
			add(s,(i-1)*m+j+1,x);
			add((i-1)*m+j,(i-1)*m+j+1,x);
			add((i-1)*m+j+1,(i-1)*m+j,x);
			ans+=x*2;
		}
	for (int i=1;i<=n;i++)
		for (int j=1;j<m;j++){
			scanf("%d",&x);
			add((i-1)*m+j,t,x);
			add((i-1)*m+j+1,t,x);
			add((i-1)*m+j,(i-1)*m+j+1,x);
			add((i-1)*m+j+1,(i-1)*m+j,x);
			ans+=x*2;
		}
	
	printf("%d\n",(ans-dinic(s,t))/2);
	
	return 0;
}