题目
（注意相邻交换指的是八连通）
思路
显然可以将黑白交换看做只有黑色棋子在空棋盘上移动
交换限制交给流量，那么有代价自然就是费用流了
考虑直接将两个相邻格子连起来，由于交换次数是相对单个格子而言的，流量无法确定
既然交换次数是单个格子的属性，自然可以考虑到拆点来表示其属性
考虑将一个格子拆成入点和出点，中间连一条边，流量为交换次数；但是想象一个黑色棋子从1->2->3，那么中间格子用了两次，两边格子只用了一次，这个路径就没法用两个点表示了
继续拆，拆成三个点，入点出点和中间点，中间点即为黑色格子所在位置，移动操作相当于中间点->出点->入点->中间点；我们在中间点->出点，入点->中间点这两个地方限流；
发现如果一个位置初始是黑点，最终是白点，那么出去的流量显然为进来的流量+1，其余同理
所以将交换次数平分给进来和出去两个地方，分情况讨论“1”的分配
其他的边很好想，连好后跑一次MCMF即可
#include<bits/stdc++.h>
#define N 2005
#define M 200005
using namespace std;
const int inf = 100000000;
int n,m,s,t,maxflow,mincost;
int pre[N],preedge[N],flow[N];
int exist[N],dis[N];
int dox[8]={-1,-1,-1,0,0,1,1,1};
int doy[8]={-1,0,1,-1,1,-1,0,1};
char st[25][25],ed[25][25],lim[25][25];
struct Edge
{
int next,to,flow,dis;
}edge[M<<1];int head[N],cnt=1;
void add_edge(int from,int to,int flow,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].flow=flow;
edge[cnt].dis=dis;
head[from]=cnt;
}
void add(int from,int to,int flow,int dis)
{
add_edge(from,to,flow,dis);
add_edge(to,from,0,-dis);
}
int get_id(int x,int y,int c) { return n*m*c + (x-1)*m + y; }
bool spfa()
{
memset(dis,50,sizeof(dis));
memset(flow,50,sizeof(flow));
queue<int> q;
dis[s]=0; q.push(s); exist[s]=1;
pre[t]=-1;
while(!q.empty())
{
int u=q.front(); q.pop(); exist[u]=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].flow && dis[v]>dis[u]+edge[i].dis)
{
pre[v]=u;
preedge[v]=i;
dis[v]=dis[u]+edge[i].dis;
flow[v]=min(flow[u],edge[i].flow);
if(!exist[v]) {exist[v]=1;q.push(v);}
}
}
}
return (pre[t] != -1);
}
void MCMF()
{
while(spfa())
{
maxflow += flow[t];
mincost += dis[t]*flow[t];
int now=t;
while(now!=s)
{
edge[preedge[now]].flow-=flow[t];
edge[preedge[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
int main()
{
scanf("%d%d",&n,&m);
s=0; t=N-1;
for(int i=1;i<=n;++i) scanf("%s",st[i]);
for(int i=1;i<=n;++i) scanf("%s",ed[i]);
for(int i=1;i<=n;++i) scanf("%s",lim[i]);
int sum=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
//入点出点
if(st[i][j-1]=='1') ++sum,add(s,get_id(i,j,1),1,0);
if(ed[i][j-1]=='1') add(get_id(i,j,1),t,1,0);
//自己连边
int l = (lim[i][j-1]-'0');
if(st[i][j-1]=='1' && ed[i][j-1]=='0')
{
add(get_id(i,j,0),get_id(i,j,1),l/2,1);
add(get_id(i,j,1),get_id(i,j,2),(l+1)/2,1);
}
else if(st[i][j-1]=='0' && ed[i][j-1]=='1')
{
add(get_id(i,j,0),get_id(i,j,1),(l+1)/2,1);
add(get_id(i,j,1),get_id(i,j,2),l/2,1);
}
else
{
add(get_id(i,j,0),get_id(i,j,1),l/2,1);
add(get_id(i,j,1),get_id(i,j,2),l/2,1);
}
//八连通
for(int k=0;k<8;++k)
{
int dx=dox[k]+i,dy=doy[k]+j;
if(dx<1 || dx>n || dy<1 || dy>m) continue;
add(get_id(i,j,2),get_id(dx,dy,0),inf,0);
}
}
}
MCMF();
if(maxflow != sum) cout<<-1<<endl;
else cout<<mincost/2<<endl;
return 0;
}