题面

大意：$n \times m$ 矩阵上的点，分成两部分，每个点分配后会有一个分数，上下左右以及中间 的五个点分到一起会有额外的分数，可以是0，求分配后最大的分数

解题思路

网络流最小割

网络流的模板并不是很难，难在建边

而对于这道题，其实是网络流中的一种标准模型吧

一个点分到A或B两部分中，不同的点组合在一起有加分的情况

用网络流的最小割做

就应该先把问题转化一下：

最优的答案当然是所有分值都加在一起咯

但是，一个点不可能同时出现在两部分，所以导致了一些不可能的情况

现在我们的目标就是去掉尽量少的分数（边权），使一个点只能出现在一个部分

这就非常符合最小割了

一开始可以先考虑把每个点拆成两个点，一个和超级源点S，另一个和超级汇点T相连

在题目中的实际意义就是这个同学是学文还是学理，边权为 他/她 的满意度，记得在这两个点之间连上一条边权为INF的边，因为同一点是不能分割的！

然后处理组合，

对于每个组合，我们新建一个结点，然后把它当做一个普通的节点处理

1和2是两个普通点，为了表示1和2的组合关系，就引入结点3当做 伪1结点 和 伪2结点，与 $1’$ 和 $2’$ 连边

$3’$ 也做同样的处理

于是就得到了下图

但是其实可以发现，这里拆点是没必要的，因为拆出的两点肯定不会被割去，且去掉中间这些容量为 $inf$ 的边，对题目并没有影响

因此可以不用拆点

建图之后跑一遍Dinic就好了

由于我们求的是最小割

所以结果应该是Ans——所有情况的满意度总和，减去Maxflow——至少删去多少边，才能满足一个同学只能选一科

Warning：

新建结点并连边的时候，不要忘记与当前的点相连

Code：

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define M 200010
#define N 40010
#define Mn 110
using namespace std;
int Cx[4]={1,0,0,-1};//上下左右
int Cy[4]={0,1,-1,0};
struct node{
    int to,cap;
    int nxt;
    node(int a,int b):to(a),cap(b){    }
    node(){    }
}b[M<<1];
int head[N],deep[N];
int n,m,S,T,t=1,Ans,Maxflow,Max;//Ans累计满意度之和
bool p[Mn][Mn];
int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
void add(int x,int y,int cap)
{
    b[++t]=node(y,cap);
    b[t].nxt=head[x];
    head[x]=t;
    b[++t]=node(x,0);
    b[t].nxt=head[y];
    head[y]=t;
    return;
}
int Cag(int x,int y)//二维转化为一维
{
    return (x-1)*m+y;
}
bool BFS()
{
    int i,cur;
    int to,cap;
    queue<int>p;
    memset(deep,0,sizeof(deep));
    deep[S]=1;p.push(S);
    while(!p.empty())
    {
        cur=p.front();p.pop();
        for(i=head[cur];i;i=b[i].nxt)
        {
            to=b[i].to;cap=b[i].cap;
            if(cap&&!deep[to])
            {
                deep[to]=deep[cur]+1;
                p.push(to);
                if(to==T)
                    return 1;
            }
        }
    }
    return 0;
}
int Dinic(int k,int flow)
{
    if(k==T)
        return flow;
    int i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt)
    {
        to=b[i].to;cap=b[i].cap;
        if(cap&&deep[to]==deep[k]+1)
        {
            res=Dinic(to,min(rest,cap));
            if(!res)
                deep[to]=0;
            b[i].cap-=res;
            b[i^1].cap+=res;
            rest-=res;
        }
    }
    return flow-rest;
}
int main()
{
    int i,j,k;
    int to,cap,flow;
    int Tx,Ty;
    n=read();m=read();
    Max=n*m;T=4*Max+1;
    for(i=1;i<=n;i++)
        p[i][0]=p[i][m+1]=1;
    for(i=1;i<=m;i++)
        p[0][i]=p[n+1][i]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            Ans+=cap=read();
            add(S,Cag(i,j),cap);//选文科
            add(Cag(i,j),Cag(i,j)+Max,INF);//自己的两个结点相连
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            Ans+=cap=read();
            add(Cag(i,j)+Max,T,cap);//选理科
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            Ans+=cap=read();
            to=Cag(i,j)+Max+Max;
            add(S,to,cap);
            add(to,Cag(i,j),INF);//别忘了自己
            for(k=0;k<4;k++)//组合
            {
                Tx=i+Cx[k];Ty=j+Cy[k];
                if(!p[Tx][Ty])
                    add(to,Cag(Tx,Ty),INF);
            }
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            Ans+=cap=read();
            to=Cag(i,j)+Max+Max+Max;
            add(to,T,cap);
            add(Cag(i,j)+Max,to,INF);
            for(k=0;k<4;k++)
            {
                Tx=i+Cx[k];Ty=j+Cy[k];
                if(!p[Tx][Ty])
                    add(Cag(Tx,Ty)+Max,to,INF);
            }
        }
    while(BFS())
        while((flow=Dinic(S,INF)))
            Maxflow+=flow;
    printf("%d",Ans-Maxflow);//最后还是挺容易的
    return 0;
}

推荐题目：

Luogu P2057 [SHOI2007]善意的投票

devil.