首先不用想，这肯定是个最小割……不妨将其解题过程记录下来，以作为一个典型的最小割模型题。
“最小割”求的是一个“最小”的值，而本题需要最大化喜悦值之和，所以很显然，在最小割中被割掉的边应该意味着“放弃该喜悦值”。也就是说，最小割是放弃掉的所有喜悦值。
首先，为了简单起见，我们不妨选取一对相邻点进行研究。不妨设是这样的：
其中S是源点，x,y是我们研究的两个点（也就是原问题中的两个学生），T是汇点。为了方便起见，没有画出边。
文中可能会用到一些符号：w(a,b)表示边(a,b)的容量，x选文的喜悦值为W_x文，x,y都选文的额外喜悦值是W_同文，以此类推。
最小割模型常用的一个手段是：每个点都需要在“在S集”和“在T集”两个事件中选一个。我们规定，“在S集”代表学文，“在T集”代表学理。
那么总的快乐值是：W_x文 + W_x理 + W_y文 + W_y理 + W_同文 + W_同理，割值就是从其中扣掉的快乐值。
下面考虑四种情况：
①x在S，y在S：
红线代表割，左边是S集，右边是T集。
割边容量之和：w(x,T) + w(y,T)
“放弃的快乐值”之和：W_x理 + W_y理 + W_同理 （两个人同时学文）
即：w(x,T) + w(y,T) = W_x理 + W_y理 + W_同理
②x在S，y在T：
x学文，y学理。
w(x,T) + w(S,y) + w(x,y) = W_x理 + W_y文 + W_同文 + W_同理
类似可以推出后两种情况：
③x在T，y在S：w(S,x) + w(y,T) + w(y,x) = W_x文 + W_y理 + W_同文 + W_同理
④x在T，y在T：w(S,x) + w(S,y) = W_x文 + W_y文 + W_同文
把四种情况写在一起：
①SS：w(x,T) + w(y,T) = W_x理 + W_y理 + W_同理
②ST：w(x,T) + w(S,y) + w(x,y) = W_x理 + W_y文 + W_同文 + W_同理
③TS：w(S,x) + w(y,T) + w(y,x) = W_x文 + W_y理 + W_同文 + W_同理
④TT：w(S,x) + w(S,y) = W_x文 + W_y文 + W_同文
然后，怎么设置这些边的容量呢？
我们看①，左边有两项，右边有三项。
秉承“对称”的思想，我们令：
w(x,T) = W_x理 + 0.5W_同理，
w(y,T) = W_y理 + 0.5W_同理。
类似地，
w(S,x) = W_x文 + 0.5W_同文，
w(S,y) = W_y文 + 0.5W_同文。
然后我们检查②和③。以②为例，将w(x,T)和w(S,y)代入并化简：
w(x,y) = 0.5 ( W_同文 + W_同理 )
同样地由③得：
w(y,x) = 0.5 ( W_同文 + W_同理 )
把x,y扩展至整张棋盘：
对于某个人(i,j)，设它对应的顶点是x。
连边(S,x)，容量为：W_x理 + 0.5 ( x和所有邻居的W_同理之和 )
连边(x,T)，容量为：W_x文 + 0.5 ( x和所有邻居的W_同文之和 )
对于某两个相邻的人x和y（y可能在x的上下左右），
连边(x,y)，容量为：0.5 ( W_同文 + W_同理 )
用所有的快乐值之和（其实就是输入的那六个矩阵的所有元素之和）减去最小割（即最大流）的值即为答案。这里有一点细节：实数容量的网络流不好求，可以把所有边的容量*2，最后输出答案时/2即可。
打代码的时候不小心把n*m打成了n+m，wa了四次，手残.......
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 #define inf 100000007
7 #define int long long
8 int read() {
9 int s=0,f=1;
10 char ch=getchar();
11 while(ch>‘9‘||ch<‘0‘) {
12 if(ch==‘-‘) {
13 f=-1;
14 }
15 ch=getchar();
16 }
17 while(ch>=‘0‘&&ch<=‘9‘) {
18 s=(s<<1)+(s<<3)+(ch^48);
19 ch=getchar();
20 }
21 return s*f;
22 }
23 int n,m,sum;
24 int wen_sin[101][101],li_sin[101][101],wen_xia[101][101],li_xia[101][101],wen_you[101][101],li_you[101][101];
25 int dis[102][102],num[101][101],zong,tot,S,T,r[10005];
26 int sum_li[10002],sum_wen[10002];
27 struct oo {
28 int to,vv,next;
29 } c[1000005];
30 void add(int x,int y,int z) {
31 c[tot].to=y;
32 c[tot].vv=z;
33 c[tot].next=r[x];
34 r[x]=tot++;
35 }
36 void init() {
37 memset(r,-1,sizeof(r));
38 n=read();
39 m=read();
40 T=n*m+1;
41 for(int i=1; i<=n; i++) {
42 for(int j=1; j<=m; j++) {
43 num[i][j]=++zong;
44 }
45 }
46 for(int i=1; i<=n; i++) {
47 for(int j=1; j<=m; j++) {
48 wen_sin[i][j]=read()*2;
49 sum+=wen_sin[i][j];
50 }
51 }
52 for(int i=1; i<=n; i++) {
53 for(int j=1; j<=m; j++) {
54 li_sin[i][j]=read()*2;
55 sum+=li_sin[i][j];
56 }
57 }
58 for(int i=1; i<n; i++) {
59 for(int j=1; j<=n; j++) {
60 wen_xia[i][j]=read()*2;
61 sum_wen[num[i][j]]+=wen_xia[i][j];
62 sum_wen[num[i+1][j]]+=wen_xia[i][j];
63 sum+=wen_xia[i][j];
64 }
65 }
66 for(int i=1; i<n; i++) {
67 for(int j=1; j<=m; j++) {
68 li_xia[i][j]=read()*2;
69 sum_li[num[i][j]]+=li_xia[i][j];
70 sum_li[num[i+1][j]]+=li_xia[i][j];
71 sum+=li_xia[i][j];
72 }
73 }
74 for(int i=1; i<=n; i++) {
75 for(int j=1; j<m; j++) {
76 wen_you[i][j]=read()*2;
77 sum_wen[num[i][j]]+=wen_you[i][j];
78 sum_wen[num[i][j+1]]+=wen_you[i][j];
79 sum+=wen_you[i][j];
80 }
81 }
82 for(int i=1; i<=n; i++) {
83 for(int j=1; j<m; j++) {
84 li_you[i][j]=read()*2;
85 sum_li[num[i][j]]+=li_you[i][j];
86 sum_li[num[i][j+1]]+=li_you[i][j];
87 sum+=li_you[i][j];
88 }
89 }
90 }
91 // S li T wen
92 void build() {
93 for(int i=1; i<=n; i++) {
94 for(int j=1; j<=m; j++) {
95 int x=li_sin[i][j]+sum_li[num[i][j]]/2;
96 add(S,num[i][j],x);
97 add(num[i][j],S,0);
98 int y=wen_sin[i][j]+sum_wen[num[i][j]]/2;
99 add(num[i][j],T,y);
100 add(T,num[i][j],0);
101 if(i<n) {
102 add(num[i][j],num[i+1][j],(li_xia[i][j]+wen_xia[i][j])/2);
103 add(num[i+1][j],num[i][j],0);
104 add(num[i+1][j],num[i][j],(li_xia[i][j]+wen_xia[i][j])/2);
105 add(num[i][j],num[i+1][j],0);
106 }
107 if(j<m) {
108 add(num[i][j],num[i][j+1],(li_you[i][j]+wen_you[i][j])/2);
109 add(num[i][j+1],num[i][j],0);
110 add(num[i][j+1],num[i][j],(li_you[i][j]+wen_you[i][j])/2);
111 add(num[i][j],num[i][j+1],0);
112 }
113 }
114 }
115 }
116 int queue[1000005],head,tail,deep[10005];
117 bool bfs(int s,int t) {
118 memset(deep,0,sizeof(deep));
119 head=tail=0;
120 deep[s]=1;
121 queue[++tail]=s;
122 while(head<tail) {
123 int opt=queue[++head];
124 for(int i=r[opt]; ~i; i=c[i].next) {
125 if(c[i].vv&&!deep[c[i].to]) {
126 deep[c[i].to]=deep[opt]+1;
127 queue[++tail]=c[i].to;
128 if(c[i].to==t) {
129 return 1;
130 }
131 }
132 }
133 }
134 return 0;
135 }
136 int dfs(int opt,int fw) {
137 if(opt==T) {
138 return fw;
139 }
140 int tmp=fw,k;
141 for(int i=r[opt]; ~i; i=c[i].next) {
142 if(tmp&&c[i].vv&&deep[c[i].to]==deep[opt]+1) {
143 k=dfs(c[i].to,min(c[i].vv,tmp));
144 if(!k) {
145 deep[c[i].to]=0;
146 continue;
147 }
148 c[i].vv-=k;
149 c[i^1].vv+=k;
150 tmp-=k;
151 }
152 }
153 return fw-tmp;
154 }
155 int dinic(int s,int t) {
156 int ans=0;
157 while(bfs(s,t)) {
158 ans+=dfs(s,inf);
159 }
160 return ans;
161 }
162 int Main(){
163 freopen("nt2011_happiness.in","r",stdin);
164 freopen("nt2011_happiness.out","w",stdout);
165 init();
166 build();
167 int ans=dinic(S,T);
168 printf("%d\n",(sum-ans)>>1);
169 return 0;
170 }
171 int hehe=Main();
172 signed main() {
173 ;
174 }
