题目描述

有一个$n$行$m$列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第$i$行第$j$列的格子只能参与$m_{i,j}$次交换。

输入格式

第一行包含两个整数$n,m$$(1<=n, m<=20)$。

以下n行为初始状态,每行为一个包含$m$个字符的$01$串,其中$0$表示黑色棋子,$1$表示白色棋子。

以下$n$行为目标状态,格式同初始状态。

以下$n$行每行为一个包含$m$个$0~9$数字的字符串,表示每个格子参与交换的次数上限。

输出格式

输出仅一行,为最小交换总次数。如果无解,输出$-1$。

样例输入

3 3
110
000
001
000
110
100
222
222
222

样例输出

4

菜鸡的咆哮

求棋盘上一个状态转移到另一个状态的最小交换次数,考虑费用流。

因为任意两个棋子交换要消耗两次交换次数(两个格子一次),所以考虑拆点。

但如果像平常拆点那样将每个点拆为入点和出点也有问题。

因为在一次连续的交换中,路径上的并非每个格子都消耗了两次交换机会。

左右端点一个换出去一次,一个换进来一次,中间的进来出去各一次。

从初态和末态来看,点的转移分为三种情况:(假定转移黑色)

①初态是黑色,末态是白色,交换出去比交换进来的次数要多一。

②初态是白色,末态是黑色,交换进来比交换出去的次数要多一。

③出态末态同色,交换进来与出去的次数相同(相当于一个中继站)。

所以考虑将一个点拆成三个:入点,中点,出点。

建图流程:

$S=>mid(初态黑色)\ f=1,w=0$

$mid(末态黑色)=>T\ f=1,w=0$

$棋盘内部八联通\ out=>in\ f=INF,w=1$

$每个点内部连接in=>mid=>out\ w=0$,根据初末态情况决定容量是$(xx+1)/2$还是$xx/2$

为什么这样可以处理两端的边界情况勒?

因为$s$和$t$都是连接点的$mid$部分,在每一次连续交换中:

起点是黑色,只会换出去一次$mid=>out$

终点是白色,只会换进来一次$in=>mid$

中间点进去一次出来一次$in=>mid=>out$

正好满足要求。

注意在判断是否有解的时候分为两种情况:

①初态黑棋子数量与末态黑棋子数量不等,显然无解。

②最大流流量与黑棋数量不等,无解。

代码

#include<bits/stdc++.h>
#define maxn 1000005
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int s,t;
struct data{
    int to;
    int p;
    int val;
    int nextt;
}line[maxn];
int first[maxn];
int tail=1;
void add(int x,int y,int w,int c){
    tail++;
    line[tail].to=y;
    line[tail].p=w;
    line[tail].val=c;
    line[tail].nextt=first[x];
    first[x]=tail;
    swap(x,y);
    tail++;
    line[tail].to=y;
    line[tail].val=-c;
    line[tail].nextt=first[x];
    first[x]=tail;
}
int dist[maxn];
int inqueue[maxn];
int pre_node[maxn];
int pre_edge[maxn];
queue<int> q;
bool SPFA(){
    while(!q.empty()) q.pop(); 
    memset(dist,0x3f,sizeof(dist));
    memset(inqueue,0,sizeof(inqueue));
    dist[s]=0;
    inqueue[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        inqueue[x]=0;
        q.pop();
        for(int i=first[x];i;i=line[i].nextt){
            int y=line[i].to;
            int w=line[i].p;
            int c=line[i].val;
            if(w&&dist[y]>dist[x]+c){
                dist[y]=dist[x]+c;
                pre_node[y]=x;
                pre_edge[y]=i;
                if(inqueue[y]==0){
                    inqueue[y]=1;
                    q.push(y);    
                }
            }
        }
    }
    return dist[t]!=inf;
}
int tot1,tot2; 
int EK(){
    int ansf=0,ansc=0;
    while(SPFA()){
        int flow=inf;
        for(int i=t;i!=s;i=pre_node[i]){
            flow=min(flow,line[pre_edge[i]].p);
        }
        for(int i=t;i!=s;i=pre_node[i]){
            line[pre_edge[i]].p-=flow;
            line[pre_edge[i]^1].p+=flow;
        }
        ansf+=flow;
        ansc+=flow*dist[t];
    }
    return ansf==tot2?ansc:-1;
}
int pos(int k,int x,int y){
    return (k-1)*n*m+(x-1)*m+y;
}
int dx[9]={0,-1,-1,-1,0,0,1,1,1};
int dy[9]={0,-1,0,1,-1,1,-1,0,1};
int to[100][100];
int from[100][100];
char x;
int main(){
    cin>>n>>m;
    s=3*n*m+1;t=s+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=8;k++){
                int ti=i+dx[k];
                int tj=j+dy[k];
                if(ti<1||ti>n||tj<1||tj>m) continue;
                add(pos(3,i,j),pos(1,ti,tj),inf,1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>x; from[i][j]=x-'0';
            if(from[i][j]) tot1++,add(s,pos(2,i,j),1,0);            
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>x; to[i][j]=x-'0';
            if(to[i][j]) tot2++,add(pos(2,i,j),t,1,0);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>x; int xx=x-'0';
            if(from[i][j]&&!to[i][j]){
                add(pos(1,i,j),pos(2,i,j),xx/2,0);    
                add(pos(2,i,j),pos(3,i,j),(xx+1)/2,0);
            }
            if(!from[i][j]&&to[i][j]){
                add(pos(1,i,j),pos(2,i,j),(xx+1)/2,0);    
                add(pos(2,i,j),pos(3,i,j),xx/2,0);
            }
            else{
                add(pos(1,i,j),pos(2,i,j),xx/2,0);    
                add(pos(2,i,j),pos(3,i,j),xx/2,0);
            }
        }
    }
    if(tot1!=tot2) puts("-1");
    else cout<<EK()<<endl;
    return 0;
}