[CQOI2012] 交换棋子 （费用流）

$pdf\space solution$    link

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<climits>

#include<queue>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

queue<int> que;

const int MAXN=;

const int N=;

struct node{

    int u,v,cost,w,nex;

}x[MAXN<<];

int head[MAXN],S,T,cnt,dis[MAXN],vis[MAXN],cost,INF=INT_MAX;

void add(int u,int v,int cost,int w){

//    printf("u:%d v:%d cost:%d w:%d\n",u,v,cost,w);

    x[cnt].u=u,x[cnt].v=v,x[cnt].cost=cost,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;swap(u,v),w=,cost=-cost;

    x[cnt].u=u,x[cnt].v=v,x[cnt].cost=cost,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;

}

bool spfa(){

    memset(dis,/,sizeof(dis)),memset(vis,,sizeof(vis));

    int inf=dis[];dis[S]=,vis[S]=,que.push(S);

    while(!que.empty()){

        int xx=que.front();que.pop();

        for(int i=head[xx];i!=-;i=x[i].nex){

            if(x[i].w&&dis[x[i].v]>dis[xx]+x[i].cost){

                dis[x[i].v]=dis[xx]+x[i].cost;

                if(!vis[x[i].v]) vis[x[i].v]=,que.push(x[i].v);

            }

        }vis[xx]=;

    }return dis[T]!=inf;

}

int dfs(int u,int flow){

//    printf("u:%d flow:%d\n",u,flow);

    if(u==T) return flow;

    int used=;vis[u]=;

    for(int i=head[u];i!=-;i=x[i].nex){

        if(x[i].w&&dis[x[i].v]==dis[u]+x[i].cost&&!vis[x[i].v]){

            int slow=dfs(x[i].v,min(flow-used,x[i].w));used+=slow;

            x[i].w-=slow,x[i^].w+=slow;

            cost+=slow*x[i].cost;

            if(used==flow) break;

        }

    }if(!used) dis[u]=-;

    vis[u]=;

    return used;

}

int dinic(){

    int ans=;cost=;

    while(spfa()){memset(vis,,sizeof(vis)),ans+=dfs(S,INF);}

    return ans;

}

char A[N][N],B[N][N],lim[N][N];

int n,m,sum;

int dx[]={,,,-,-,-,,};

int dy[]={,,-,,,-,,-};

int Q(int x,int y){return (x-)*m+y;}

int main(){

//    freopen("8.in","r",stdin);

    memset(head,-,sizeof(head));

    n=read(),m=read();S=,T=n*m*+;

    for(int i=;i<=n;i++) scanf("%s",A[i]+);

    for(int i=;i<=n;i++) scanf("%s",B[i]+);

    for(int i=;i<=n;i++) scanf("%s",lim[i]+);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++){

            if(A[i][j]==B[i][j]&&A[i][j]==) continue;

            A[i][j]-='',B[i][j]-='',lim[i][j]-='';

            if(A[i][j]==B[i][j]){

                    add(Q(i,j),Q(i,j)+n*m,,lim[i][j]/);

                    add(Q(i,j)+*n*m,Q(i,j),,lim[i][j]);

                continue;

            }

            if(A[i][j]==){

                sum++;

                add(S,Q(i,j),,);

                add(Q(i,j),Q(i,j)+n*m,,(lim[i][j]+)/);

                add(Q(i,j)+*n*m,Q(i,j),,(lim[i][j]-)/);

                continue;

            }

            if(B[i][j]==){

                add(Q(i,j),Q(i,j)+n*m,,(lim[i][j]-)/);

                add(Q(i,j)+*n*m,Q(i,j),,(lim[i][j]+)/);

                add(Q(i,j),T,,);

            }

        }

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            for(int k=;k<;k++){

                int bx=i+dx[k],by=j+dy[k];

                if(bx>=&&bx<=n&&by>=&&by<=m){

                    add(Q(i,j)+n*m,Q(bx,by)+*n*m,,INF);

                }

            }

        }

    }

    int Ans=dinic();

    if(Ans!=sum){printf("-1");return ;}

    printf("%d\n",cost);

}/*

1 2

1 0

0 1

1 1

*/