题目描述
有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与mi,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
题解
费用流好题（说的清楚一点就是我根本不会做……）
%%%大佬->这里
首先考虑，我们可以把交换操作，看作是黑色的点在移动
一个点往下移动的话，当前点和下方的点的交换次数都加一
然后一条移动的路径，两端的点移动次数加一，中间的点移动次数加二
如果把这个过程看做网络流的话，就会有一个问题。因为每一个点开始和结束的颜色可能不同，那么流入和流出也不同
如果只有一个点，就没办法考虑交换次数的限制
而且如果只拆成两个点的话，就没办法考虑路径两端的情况了
那么我们把每一个点拆成三个点$left,now,right$，分别表示只有流入，有流入和流出，只有流出
所以连边$left->now->right$
然后相互能到达的点之间连边，容$inf$费$0$
然后考虑如何解决流入流出不平衡
如果开始为白，之后黑，那么流出必定比流入多一，开始黑，之后白，流入必定比流出多一，颜色一样，那么流入流出一样
然后交换次数最少，在相邻的格子的边上加上费用
若该点在初始图中是黑的、最终图中是白的，那么连边$(left,now,1,\frac{limit}{2}),(now,right,1,\frac{limit+1}{2})$
若该点在初始图中是白的、最终图中是黑的，那么连边$(left,now,1,\frac{limit+1}{2}),(now,right,1,\frac{limit}{2})$
若该点在初始图和最终图中颜色相同，那么连边$(left,now,1,\frac{limit}{2}),(now,right,1,\frac{limit}{2})$
这样就可以保证流量限制了
然后加源，往起始的所有黑点连边，加汇，让最终所有黑点往它连边
然后在能互相到达的点之间连边
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
#define l(i,j) ((i-1)*m+j)
#define now(i,j) (((i-1)*m+j)+n*m)
#define r(i,j) (((i-1)*m+j)+(n*m<<1))
using namespace std;
const int N=,M=;
int dx[]={,,,,-,-,-,},dy[]={,,-,-,-,,,};
int ver[M],Next[M],head[N],flow[M],edge[M],tot=;
int dis[N],disf[N],Pre[N],last[N],vis[N];
int n,m,ans=,S,T;
queue<int> q;
inline void add(int u,int v,int f,int e){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,flow[tot]=f,edge[tot]=e;
ver[++tot]=u,Next[tot]=head[v],head[v]=tot,flow[tot]=,edge[tot]=-e;
}
bool spfa(){
memset(dis,0x3f,sizeof(dis));
q.push(S),dis[S]=,disf[S]=inf,Pre[T]=-;
while(!q.empty()){
int u=q.front();q.pop(),vis[u]=;
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(flow[i]&&dis[v]>dis[u]+edge[i]){
dis[v]=dis[u]+edge[i],Pre[v]=u,last[v]=i;
disf[v]=min(disf[u],flow[i]);
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return ~Pre[T];
}
int dinic(){
int maxflow=;
while(spfa()){
int u=T;maxflow+=disf[T],ans+=disf[T]*dis[T];
while(u!=S){
flow[last[u]]-=disf[T];
flow[last[u]^]+=disf[T];
u=Pre[u];
}
}
return maxflow;
}
int x1[][],x2[][],t1,t2;
char s[];
int main(){
scanf("%d%d",&n,&m);
S=,T=n*m*+;
for(int i=;i<=n;++i){
scanf("%s",s+);
for(int j=;j<=m;++j)
if(s[j]==''){
++t1,add(S,now(i,j),,);
x1[i][j]=;
}
}
for(int i=;i<=n;++i){
scanf("%s",s+);
for(int j=;j<=m;++j)
if(s[j]==''){
++t2,add(now(i,j),T,,);
x2[i][j]=;
}
}
if(t1!=t2) return puts("-1"),;
for(int i=;i<=n;++i){
scanf("%s",s+);
for(int j=;j<=m;++j){
t2=s[j]-'';
if(x1[i][j]==x2[i][j])
add(l(i,j),now(i,j),t2/,),add(now(i,j),r(i,j),t2/,);
else if(x1[i][j]&&!x2[i][j])
add(l(i,j),now(i,j),t2/,),add(now(i,j),r(i,j),(t2+)/,);
else
add(l(i,j),now(i,j),(t2+)/,),add(now(i,j),r(i,j),t2/,);
}
}
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
for(int k=;k<;++k){
int ti=i+dx[k],tj=j+dy[k];
if(ti<||ti>n||tj<||tj>m) continue;
add(r(i,j),l(ti,tj),inf,);
}
if(dinic()!=t1) return puts("-1"),;
printf("%d\n",ans);
return ;
}