题目
题目描述
有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。
输入输出格式
输入格式：
第一行包含两个整数n，m（1<=n, m<=20）。以下n行为初始状态，每行为一个包含m个字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行为目标状态，格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串，表示每个格子参与交换的次数上限。
输出格式：
输出仅一行，为最小交换总次数。如果无解，输出-1。
输入输出样例
输入样例#1：
3 3
110
000
001
000
110
100
222
222
222
输出样例#1：
4
题解
这个拆点真的很神仙啊……
首先发现题目可以转换成一个棋盘，上面有$k$个黑子，要求移动黑子到指定位置形成最终的棋盘
发现有这么个性质：
一条路径路径起点和终点花费次数为$1$，路径中每个点的花费次数为$2$
比如$a\rightarrow b\rightarrow c$，$a,c$交换$1$次，$b$位置要跟$a,c$都交换一次，所以花费$2$次
进一步推出：如果把交换次数分开看成进入次数$d1$和出去次数$d2$，初始为黑点的位置$d2=d1+1$，结束为黑点的位置$d1=d2+1$，其他点$d1=d2$
这个也不难证明，如果初始为黑点，说明这个位置肯定是某个路径的起点；如果结束为黑点，说明这个位置肯定是某个路径的终点
所以把每个位置拆成$3$个点$a_i,b_i,c_i$，$a_i$表示流入，$c_i$表示流出
这样建边就比较明了了：$(u,v,flow,cost)$
初始为黑点，结束为白点：$(S\rightarrow b_i,1,0),(a_i\rightarrow b_i,\left\lfloor\frac{m_i}{2}\right\rfloor,0),(b_i\rightarrow c_i,\left\lfloor\frac{m_i+1}{2}\right\rfloor,0)$（表示$d2=d1+1$）
初始为白点，结束为黑点：$(b_i\rightarrow T,1,0),(a_i\rightarrow b_i,\left\lfloor\frac{m_i+1}{2}\right\rfloor,0),(b_i\rightarrow c_i,\left\lfloor\frac{m_i}{2}\right\rfloor,0)$（表示$d1=d2+1$）
其他：$(a_i\rightarrow b_i,\left\lfloor\frac{m_i}{2}\right\rfloor,0),(b_i\rightarrow c_i,\left\lfloor\frac{m_i}{2}\right\rfloor,0)$（表示$d1=d2$，交换次数肯定为偶数）
$i$能与$j$交换：$(c_i\rightarrow a_i,inf,1)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define pu(x,y) ((x-1)*m+y)
using namespace std;
const int MAX=2e5+5,inf=1e9;
struct p{
int x,y,dis,cn;
}c[MAX];
int n,m,num=1,T;
int h[MAX],d[MAX],pre[MAX],qu[MAX];
char s[3][21][21];
bool use[MAX];
void add(int x,int y,int dis,int cn)
{
c[++num]=(p){h[x],y,dis,cn},h[x]=num;
c[++num]=(p){h[y],x,0,-cn},h[y]=num;
}
pair<int,int> EK()
{
int hl,tl,tot=0,tot1=0;
while(1)
{
memset(d,1,sizeof(d));
d[0]=0,hl=tl=1;
while(hl<=tl)
{
int tt=qu[hl++];
use[tt]=0;
for(int i=h[tt];i;i=c[i].x)
if(d[c[i].y]>d[tt]+c[i].cn&&c[i].dis)
{
d[c[i].y]=d[tt]+c[i].cn,pre[c[i].y]=i;
if(!use[c[i].y]) use[c[i].y]=1,qu[++tl]=c[i].y;
}
}
if(d[T]>1e7) return make_pair(tot1,tot);
int hh=T,sum=1e9,l;
while(hh) l=pre[hh],sum=min(sum,c[l].dis),hh=c[l^1].y;
hh=T,tot1+=sum;
while(hh) l=pre[hh],c[l].dis-=sum,c[l^1].dis+=sum,tot+=sum*c[l].cn,hh=c[l^1].y;
}
}
int main()
{
scanf("%d%d",&n,&m),T=3*n*m+1;
int N=n*m,sum=0,tot=0;
pair<int,int> ans;
for(int i=1;i<=n;++i)
scanf("%s",s[0][i]+1);
for(int i=1;i<=n;++i)
scanf("%s",s[1][i]+1);
for(int i=1,x;i<=n;++i)
{
scanf("%s",s[2][i]+1);
for(int j=1;j<=m;++j)
{
if(s[0][i][j]=='0') ++sum;
if(s[1][i][j]=='0') ++tot;
x=s[2][i][j]-'0';
if(s[0][i][j]==s[1][i][j]) add(pu(i,j),pu(i,j)+N,x>>1,0),add(pu(i,j)+N,pu(i,j)+2*N,x>>1,0);
if(s[0][i][j]=='0'&&s[1][i][j]=='1') add(pu(i,j),pu(i,j)+N,x>>1,0),add(pu(i,j)+N,pu(i,j)+2*N,x+1>>1,0);
if(s[0][i][j]=='1'&&s[1][i][j]=='0') add(pu(i,j),pu(i,j)+N,x+1>>1,0),add(pu(i,j)+N,pu(i,j)+2*N,x>>1,0);
if(s[0][i][j]=='0') add(0,pu(i,j)+N,1,0);
if(s[1][i][j]=='0') add(pu(i,j)+N,T,1,0);
if(i>1)
{
add(pu(i,j)+2*N,pu(i-1,j),inf,1);
if(j>1) add(pu(i,j)+2*N,pu(i-1,j-1),inf,1);
if(j<m) add(pu(i,j)+2*N,pu(i-1,j+1),inf,1);
}
if(i<n)
{
add(pu(i,j)+2*N,pu(i+1,j),inf,1);
if(j>1) add(pu(i,j)+2*N,pu(i+1,j-1),inf,1);
if(j<m) add(pu(i,j)+2*N,pu(i+1,j+1),inf,1);
}
if(j>1) add(pu(i,j)+2*N,pu(i,j-1),inf,1);
if(j<m) add(pu(i,j)+2*N,pu(i,j+1),inf,1);
}
}
if(sum!=tot) return printf("-1"),0;
if((ans=EK()).first!=sum) return printf("-1"),0;
return printf("%d",ans.second),0;
}
