题目大意:
每个人都有两个选择,选择文科会获得$w_i$的收益,选择文科会获得$l_i$的收益。有些特定的一对,如果他们同时选择某一科目,又会有相应的收益。求收益最大。

题解:
这里用到了网络流二元组建图。所谓网络流其实也就是线性规划转成图论,二元组建图也同样是这样。
这题建图如下:
网络流二元组建图

题目要求使收益最大,于是我们想到用总收益减去最小割,这里的最小割即损失的收益最小。于是我们割的边代表着损失的代价。
我们现在做的就只需要列出方程并解出所有变量的值即可:
$$\begin{cases}
a+b=w_1+w_2+w_{12}\\
c+d=l_1+l_2+l_{12}\\
a+e+d=w_1+l_2+w_{12}+l_{12}\\
b+e+c=w_2+l_1+w_{12}+l_{12}\\
\end{cases}$$
解得:
$$\begin{cases}
a=w_1+{w_{12}\over 2}\\
b=w_2+{w_{12}\over 2}\\
c=l_1+{l_{12}\over 2}\\
d=l_2+{l_{12}\over 2}\\
e={w_{12}\over 2}+{l_{12}\over 2}
\end{cases}$$
依此建图跑出最小割,用总收益减去即可,这里可以将边权扩大两倍使得边权均为整数。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 10005
#define M 1000005
#define REP(a,l,r) for(int a=l; a<=r; a++)
using namespace std;
int n, m, SUM, S, T;
int dis[N];
struct Edge {
    int nex, to, flow;
} e[M];
int head[N], cnt;
int w[105][105], l[105][105], ws[105][105], ls[105][105], wh[105][105], lh[105][105];
inline int id(int x, int y) { return (x-1)*m+y; }

void Link(int x, int y, int z) {
    e[++cnt].nex = head[x]; head[x] = cnt;
    e[cnt].to = y; e[cnt].flow = z;
}
void ins1(int x, int y, int z) { Link(x,y,z); Link(y,x,0); }
void ins2(int x, int y, int z) { Link(x,y,z); Link(y,x,z); }

void Input() {
    scanf("%d%d", &n, &m); S=0; T=n*m+1;
    REP(i,1,n) REP(j,1,m) scanf("%d", &w[i][j]), SUM += w[i][j], w[i][j]<<=1;
    REP(i,1,n) REP(j,1,m) scanf("%d", &l[i][j]), SUM += l[i][j], l[i][j]<<=1;
    REP(i,1,n-1) REP(j,1,m) scanf("%d", &ws[i][j]);
    REP(i,1,n-1) REP(j,1,m) scanf("%d", &ls[i][j]);
    REP(i,1,n) REP(j,1,m-1) scanf("%d", &wh[i][j]);
    REP(i,1,n) REP(j,1,m-1) scanf("%d", &lh[i][j]);
}

void Build_map() {
    memset(head, 0, sizeof(head));
    cnt = 1;
    REP(i,1,n-1) REP(j,1,m) {
        SUM += ws[i][j] + ls[i][j];
        w[i][j] += ws[i][j]; w[i+1][j] += ws[i][j];
        l[i][j] += ls[i][j]; l[i+1][j] += ls[i][j];
        ins2(id(i,j), id(i+1,j), ws[i][j] + ls[i][j]);
    }
    REP(i,1,n) REP(j,1,m-1) {
        SUM += wh[i][j] + lh[i][j];
        w[i][j] += wh[i][j]; w[i][j+1] += wh[i][j];
        l[i][j] += lh[i][j]; l[i][j+1] += lh[i][j];
        ins2(id(i,j), id(i,j+1), wh[i][j] + lh[i][j]);
    }
    REP(i,1,n) REP(j,1,m) {
        ins1(S, id(i,j), w[i][j]);
        ins1(id(i,j), T, l[i][j]);
    }
}

bool BFS() {
    queue<int> Q;
    memset(dis, -1, sizeof(dis));
    Q.push(0); dis[0] = 0;
    while( !Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int j=head[u]; j; j=e[j].nex)
        if(e[j].flow && dis[e[j].to]<0) {
            dis[e[j].to] = dis[u] + 1;
            Q.push(e[j].to);
        }
    }
    return dis[T] > 0;
}

int DFS(int p, int minF) {
    if(p == T) return minF;
    int a, minf = minF;
    for(int j=head[p]; j; j=e[j].nex)
    if(e[j].flow && dis[e[j].to] == dis[p]+1) {
        a = DFS(e[j].to, min(minf, e[j].flow));
        e[j].flow -= a; e[j^1].flow += a;
        minf -= a; if(minf == 0) break;
    }
    return minF - minf;
}

int Dinic() {
    int ans = 0;
    while(BFS()) ans += DFS(S, 1000000000);
    return ans;
}

int main() {
    Input();
    Build_map();
    printf("%d\n", SUM - (Dinic()>>1));
    return 0;
}