• 这题学长说可以转化为最大权闭合子图，然鹅我当时没有听懂。看了题解，大家有的在列方程搞事情，我也不是很懂。有一篇博客给了一张图，我拿着图搞了搞，好像会了一种算法。（不算是自己想出来的吧，图已经给了大致思路，只能说细节是自己实现的）。
• 先来盗一下图。
• 这个图好nb，看懂这张图这题基本就做完了。我们要给每个人选一个科目，让总的价值最大。这类问题如何用网络流解呢？还是从简入手，我们先考虑只有两个人的情况，这就是这张图的由来。
• 两个人有四种情况，（\(x\)选文，\(y\)选理）、（\(x\)选理，\(y\)选文）、（两人都选文）、（两人都选理）。题目让求最大值，而我们网络流求最大流最小割，求的都是最小值。因此，我们需要转化一下。先把所有情况对答案的贡献累加，然后跑最小割去掉最小代价使方案合法。
• 我们先把\(x\)选文、\(x\)选理、\(y\)选文、\(y\)选理、\(x\)和\(y\)都选文、\(x\)和\(y\)都选理的代价累加。这时，按照图中那样建图，割掉一条边代表不使用这个状态。从\(S\)到\(x\)连一条边，代表\(x\)选了文，其他同理。向\(T\)连边代表选了理。你发现，这样建图的好处在于，你割的方案正好对应了四种情况。
• 这时候，就是合理给边赋值，跑最小割了。使\(S\)到\(x\)的边容量为\(x\)选文的价值加上同时选文价值的一半。\(y\)同理。使\(x\)到\(T\)的边容量为\(x\)选理的价值加上同选理的价值的一半，\(y\)同理。\(x\)向\(y\)连边的容量为同选文价值的一半加上同选理价值的一半。这样，假如你割掉了\(a\)，\(d\)，那么你必须割掉\(e\)。代表你选择去掉\(x\)选文的情况、\(y\)选理的情况，答案就是初始\(sum-maxflow\)。
• 拓展到多点也是一样，注意这题卡精度，可以先把权值乘2最后再除掉。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e4+10;
const int M=2e5+10;
const int inf=1e9;
map<pair<int,int>,int>w;
int n,m,s,t,tot=1,we[N],li[N],ver[M],Next[M],lin[N],edge[M],d[N],maxflow,flow,sum;
int cal(int i,int j){return (i-1)*m+j;}
void add(int x,int y,int z){
    ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;
    ver[++tot]=x;Next[tot]=lin[y];lin[y]=tot;edge[tot]=0;
}
bool bfs(){
    memset(d,0,sizeof(d));
    queue<int>q;
    d[s]=1,q.push(s);
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=lin[x];i;i=Next[i]){
            int y=ver[i];
            if(!d[y]&&edge[i]){
                d[y]=d[x]+1;
                q.push(y);
                if(y==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow;
    for(int i=lin[x];i&&rest;i=Next[i]){
        int y=ver[i];
        if(d[y]==d[x]+1&&edge[i]){
            int k=dinic(y,min(edge[i],rest));
            if(!k) d[y]=0;
            rest-=k;edge[i]-=k;edge[i^1]+=k;
            if(!rest) return flow-rest;
        }
    }
    return flow-rest;
}
int main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&we[cal(i,j)]),sum+=we[cal(i,j)],we[cal(i,j)]*=2;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&li[cal(i,j)]),sum+=li[cal(i,j)],li[cal(i,j)]*=2;
    for(int i=2;i<=n;++i) for(int j=1;j<=m;++j){
        int c;scanf("%d",&c);sum+=c;
        c*=2;
        we[cal(i,j)]+=c/2;we[cal(i-1,j)]+=c/2;
        w[make_pair(cal(i,j),cal(i-1,j))]=c/2;
    }
    for(int i=2;i<=n;++i) for(int j=1;j<=m;++j){
        int c;scanf("%d",&c);sum+=c;
        c*=2;
        li[cal(i,j)]+=c/2;li[cal(i-1,j)]+=c/2;
        c/=2;
        c+=w[make_pair(cal(i,j),cal(i-1,j))];
        add(cal(i,j),cal(i-1,j),c);add(cal(i-1,j),cal(i,j),c);
    }
    for(int i=1;i<=n;++i) for(int j=2;j<=m;++j){
        int c;scanf("%d",&c);sum+=c;
        c*=2;
        we[cal(i,j)]+=c/2;we[cal(i,j-1)]+=c/2;
        w[make_pair(cal(i,j),cal(i,j-1))]=c/2;
    }
    for(int i=1;i<=n;++i) for(int j=2;j<=m;++j){
        int c;scanf("%d",&c);sum+=c;
        c*=2;
        li[cal(i,j)]+=c/2;li[cal(i,j-1)]+=c/2;
        c/=2;
        c+=w[make_pair(cal(i,j),cal(i,j-1))];
        add(cal(i,j),cal(i,j-1),c);add(cal(i,j-1),cal(i,j),c);
    }
    s=0,t=n*m+1;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
        add(s,cal(i,j),we[cal(i,j)]);
        add(cal(i,j),t,li[cal(i,j)]);
    }
    while(bfs()){
        while(flow=dinic(s,inf)) maxflow+=flow;
    }
    printf("%d\n",sum-maxflow/2);
    return 0;
}