【BZOJ2127】happiness（网络流）

建模：

首先 \(S\) 向每一个 \((i,j)\) 连一条它选文科的价值的边，每一个 \((i,j)\) 向 \(T\) 连一条它选理科的价值的边。

然后对于两个点 \(a,b\)，假设他们同时选理科能获得价值 \(x\)，那么新建一个节点 \(newnode\)，连 \((S,newnode,x)\)，\((newnode,a,\inf)\)，\((newnode,b,\inf)\)。

大概建出来的图长这样。

然后用最小割割掉的是我们不需要的价值，用 \(sum\) 减去最小割就好了。

代码：

#include<bits/stdc++.h>
 
#define N 110
#define NN N*N*5
#define NM (N*N*2+N*N*4*3)*2
#define get(i,j) ((i-1)*m+j)
#define get2(i,j) ((i-1)*(m-1)+j)
#define INF 0x7fffffff
 
using namespace std;
 
int n,m,s,t,sum;
int cnt=1,head[NN],cur[NN],to[NM],nxt[NM],c[NM];
int num[NN];
 
queue<int>q;
 
void adde(int u,int v,int ci)
{
    to[++cnt]=v;
    c[cnt]=ci;
    nxt[cnt]=head[u];
    head[u]=cnt;
     
    to[++cnt]=u;
    c[cnt]=0;
    nxt[cnt]=head[v];
    head[v]=cnt;
}
 
bool bfs()
{
    memcpy(cur,head,sizeof(cur));
    memset(num,-1,sizeof(num));
    num[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i])
        {
            int v=to[i];
            if(c[i]&&num[v]==-1)
            {
                num[v]=num[u]+1;
                q.push(v);
            }
        }
    }
    return num[t]!=-1;
}
 
int dfs(int u,int minflow)
{
    if(!minflow||u==t) return minflow;
    int preflow=0,nowflow;
    for(int i=cur[u];i;i=nxt[i])
    {
        cur[u]=i;
        int v=to[i];
        if(num[v]==num[u]+1&&(nowflow=dfs(v,min(minflow-preflow,c[i]))))
        {
            preflow+=nowflow;
            c[i]-=nowflow;
            c[i^1]+=nowflow;
            if(!(minflow-preflow)) break;
        }
    }
    return preflow;
}
 
int dinic()
{
    int maxflow=0;
    while(bfs())
        maxflow+=dfs(s,INF);
    return maxflow;
}
 
int main()
{
    scanf("%d%d",&n,&m);
    s=1,t=1+n*m+(n-1)*m*2+n*(m-1)*2+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            adde(s,1+get(i,j),x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            adde(1+get(i,j),t,x);
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            int newnode=1+n*m+get(i,j);
            adde(s,newnode,x);
            adde(newnode,1+get(i,j),INF);
            adde(newnode,1+get(i+1,j),INF);
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            int newnode=1+n*m+(n-1)*m+get(i,j);
            adde(1+get(i,j),newnode,INF);
            adde(1+get(i+1,j),newnode,INF);
            adde(newnode,t,x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            int newnode=1+n*m+(n-1)*m*2+get2(i,j);
            adde(s,newnode,x);
            adde(newnode,1+get(i,j),INF);
            adde(newnode,1+get(i,j+1),INF);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            int newnode=1+n*m+(n-1)*m*2+n*(m-1)+get2(i,j);
            adde(1+get(i,j),newnode,INF);
            adde(1+get(i,j+1),newnode,INF);
            adde(newnode,t,x);
        }
    }
    printf("%d\n",sum-dinic());
    return 0;
}