文理分科

题目链接：https://cn.vjudge.net/contest/281959#problem/D
解题思路：二元组建图后跑最大流（等于最小割）
参考题解：http://www.cnblogs.com/chenyushuo/p/5146626.html?tdsourcetag=s_pctim_aiomsg
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf=2147483647;
struct node
{
    int next,to,dis;
}edge[600030];
int head[100010],cur[100010],deep[100010];
int n,m,cnt=2,maxflow;
int nextt[4][2]={{0,1},{1,0},{-1,0},{0,-1}};

void addedge(int from,int to,int dis)
{
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    edge[cnt].next=head[from];
    head[from]=cnt++;

    edge[cnt].to=from;
    edge[cnt].dis=0;
    edge[cnt].next=head[to];
    head[to]=cnt++;
}

bool bfs(int s,int t)
{
    memset(deep,0,sizeof(deep));
    queue<int>q;
    while(!q.empty())
        q.pop();
    memcpy(cur,head,sizeof(head));
    deep[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=-1;i=edge[i].next)
        {
            if(!deep[edge[i].to]&&edge[i].dis)
            {
                deep[edge[i].to]=deep[now]+1;
                q.push(edge[i].to);
            }
        }
    }
    return deep[t];
}

int dfs(int now,int t,int limit)
{
    if(!limit||now==t)
        return limit;
    int flow=0;
    for(int i=cur[now];i!=-1;i=edge[i].next)
    {
//        cur[now]=i;
//        if(deep[edge[i].to]==deep[now]+1&&(
//           f=dfs(edge[i].to,t,min(limit,edge[i].dis))))
//        {
//            flow+=f;
//            limit-=f;
//            edge[i].dis-=f;
//            edge[i^1].dis+=f;
//            if(!limit)break;
//        }
        if(edge[i].dis&&deep[edge[i].to]==deep[now]+1)
        {
            int d=dfs(edge[i].to,t,min(limit,edge[i].dis));
            flow+=d;
            limit-=d;
            edge[i].dis-=d;
            edge[i^1].dis+=d;
        }
    }
    if(!flow)deep[now]=0;
    return flow;
}

void dinic(int s,int t)
{
    while(bfs(s,t))
        maxflow+=dfs(s,t,inf);
}

int hashh[111][111],tot=0;

int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    int summ=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            hashh[i][j]=++tot;
        }
    }
    cnt=0;
    int s,t;
    s=0;
    t=tot*3+1;
    int d;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>d;
            summ+=d;
            addedge(s,hashh[i][j],d);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>d;
            summ+=d;
            addedge(hashh[i][j],t,d);
        }
    }

    int now=tot;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>d;
            summ+=d;
            now++;
            addedge(now,hashh[i][j],inf);
            for(int k=0;k<4;k++)
            {
                int tx=i+nextt[k][0],ty=j+nextt[k][1];
                if(!tx||tx>n||!ty||ty>m)continue;
                addedge(now,hashh[tx][ty],inf);
            }
            addedge(s,now,d);
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>d;
            now++;
            summ+=d;
            addedge(hashh[i][j],now,inf);
            for(int k=0;k<4;k++)
            {
                int tx=i+nextt[k][0],ty=j+nextt[k][1];
                if(!tx||tx>n||!ty||ty>m)continue;
                addedge(hashh[tx][ty],now,inf);
            }
            addedge(now,t,d);
        }
    }
    maxflow=0;
    dinic(s,t);
    cout<<summ-maxflow<<endl;
    return 0;
}