传送门

题意：

高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。

n,m<=100

Solution：

看到这道题首先想到dp，但是在转移的时候发现需要记录的东西太多，然后便陷入江局。。。

最后发现是网络流，果然网络流是我永远主动想不出来的。。。

说下建图方法：

对于每个人，我们从S向这个人连容量为 ai,j a i , j 的边，表示选文科，从这个人向T连容量为 bi,j b i , j 的边，表示选理科；

对于都选文科的收益，我们新建一个点，从S向这个点连容量为收益的边，从这个点向对应的两个点连容量为INF的边；

对于都选理科的收益，我们新建一个点，从这个点向T连容量为收益的边，从对应的两个点向这个点连容量为INF的边。

考虑从这个网络流里删边，最后剩下的边是最终产生的合法收益，我们发现如果从S到T有一条通路，那么剩下的边一定会产生矛盾，所以我们只要求最小割即可。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int inf=1e9;
const int N=10010;
struct edg{
    int to,next,flow;
}e[28*N];
int dep[5*N],S,T,head[5*N],size=1,tot,q[5*N],n,m,ans,v[5*N];
int calc(int x,int y){
  return (x-1)*m+y;}
void add(int x,int y,int f)
{
    size++;e[size].to=y;e[size].next=head[x];e[size].flow=f;head[x]=size;
    size++;e[size].to=x;e[size].next=head[y];e[size].flow=0;head[y]=size;
}
bool bfs()
{
    int h=0,t=0;
    memset(dep,0,sizeof(dep));
    dep[S]=1,q[++t]=S;
    while (h<t)
    {
        int x=q[++h];
        for (int i=head[x];i;i=e[i].next)
        {
            int y=e[i].to;
            if (!dep[y]&&e[i].flow) dep[y]=dep[x]+1,q[++t]=y;
        }
    }
    return (dep[T]!=0);
}
int dfs(int x,int flow)
{
    if (x==T) return flow;
    int now=0,used=0;
    for (int i=v[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if (e[i].flow&&dep[y]==dep[x]+1)
        {
            now=dfs(y,min(e[i].flow,flow-used));
            used+=now;
            e[i].flow-=now;
            e[i^1].flow+=now;
            v[x]=i;
            if (flow==used) break;
        }
    }
    if (used==0) dep[x]=-1;
    return used;
}
int main()
{
    scanf("%d%d",&n,&m);S=0,T=n*m+1;tot=T;int x;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) scanf("%d",&x),add(S,calc(i,j),x),ans+=x;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) scanf("%d",&x),add(calc(i,j),T,x),ans+=x;
    for (int i=1;i<n;i++)
        for (int j=1;j<=m;j++) scanf("%d",&x),tot++,add(S,tot,x),add(tot,calc(i,j),inf),add(tot,calc(i+1,j),inf),ans+=x;
    for (int i=1;i<n;i++)
        for (int j=1;j<=m;j++) scanf("%d",&x),tot++,add(tot,T,x),add(calc(i,j),tot,inf),add(calc(i+1,j),tot,inf),ans+=x;
    for (int i=1;i<=n;i++)
        for (int j=1;j<m;j++) scanf("%d",&x),tot++,add(S,tot,x),add(tot,calc(i,j),inf),add(tot,calc(i,j+1),inf),ans+=x;
    for (int i=1;i<=n;i++)
        for (int j=1;j<m;j++) scanf("%d",&x),tot++,add(tot,T,x),add(calc(i,j),tot,inf),add(calc(i,j+1),tot,inf),ans+=x;
    while (bfs())
    {
        for (int i=0;i<=tot;i++) v[i]=head[i];
        ans-=dfs(S,inf);
    }
    printf("%d",ans);
}