BZOJ3774:最优选择 网络流

思路:

首先由于是一个二分图,我们分为左右两部分.

...然后具体的建模自己看代码吧,真的是好神奇的思路...

我居然连这都想不出来真是混不下去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int INF=0x3f3f3f3f;
struct MaxflowSolver{
    static const int V=5010;
    static const int E=80010;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline bool bfs(int S,int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
        }return d[T]!=-1;
    }
    inline int dinic(int p,int T,int Maxflow){
        if(p==T)return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[p]+1==d[end[j]]){
            int to=dinic(end[j],T,last>flow[j]?flow[j]:last);if(to)flow[j]-=to,flow[j^1]+=to,last-=to;
            if(!last)return Maxflow;
        }
        d[p]=-1;return Maxflow-last;
    }
    inline int Maxflow(int S,int T){
        int res=0;
        while(bfs(S,T))res+=dinic(S,T,INF);
        return res;
    }
}Stg;
 
int lab[51][51][2],a[51][51],b[51][51];
 
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j,k;int x,res=0;
     
    int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)lab[i][j][0]=++id,lab[i][j][1]=++id;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&b[i][j]),res+=b[i][j];
     
    int S=0,T=id+1;
     
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j){
        if((i+j)&1)Stg.make(S,lab[i][j][0],a[i][j]),Stg.make(lab[i][j][0],lab[i][j][1],b[i][j]);
        else Stg.make(lab[i][j][1],lab[i][j][0],b[i][j]),Stg.make(lab[i][j][0],T,a[i][j]);
        for(k=0;k<4;++k){
            int nowx=i+dx[k],nowy=j+dy[k];
            if(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m){
                if((i+j)&1)Stg.make(lab[i][j][0],lab[nowx][nowy][1],INF);
                else Stg.make(lab[nowx][nowy][1],lab[i][j][0],INF);
            }
        }
    }
     
    printf("%d",res-Stg.Maxflow(S,T));
     
    return 0;
}