题目链接
题解
容易想到由\(S\)向初始的黑点连边，由终态的黑点向\(T\)连边，然后相邻的点间连边
但是这样满足不了交换次数的限制，也无法计算答案
考虑如何满足一个点的交换次数限制
当然是拆点
但是一个位置被经过时会被交换两次，而终点和起点都只交换了一次
那么我们就拆成三个点\(left\)，\(mid\)，\(right\)，分别管理入，中介，出
它们之间顺次两边，费用为\(1\)
流量将限制\(lim\)拆开，当\(lim\)为奇数时要考虑给哪一边：
如果该点一开始是黑点，终态是白点，那么这个点出边一定比入边多
如果一开始是白点，终态是黑点，那么一定要入边多一点
否则一样多
有一些要注意的地方：
①要判黑白起始是否相同
②相邻不止是四个方向
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 2005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int h[maxn],ne = 1;
struct EDGE{int to,nxt,f,w;}ed[maxm];
inline void build(int u,int v,int f,int w){
ed[++ne] = (EDGE){v,h[u],f,w}; h[u] = ne;
ed[++ne] = (EDGE){u,h[v],0,-w}; h[v] = ne;
}
int d[maxn],minf[maxn],vis[maxn],p[maxn],S,T;
int q[maxn * 10],head,tail;
int mincost(){
int flow = 0,cost = 0,u;
while (true){
for (int i = S; i <= T; i++) vis[i] = 0,d[i] = minf[i] = INF;
d[S] = 0; q[head = tail = 0] = S;
while (head <= tail){
u = q[head++];
vis[u] = false;
Redge(u) if (ed[k].f && d[u] + ed[k].w < d[to = ed[k].to]){
d[to] = d[u] + ed[k].w; p[to] = k; minf[to] = min(ed[k].f,minf[u]);
if (!vis[to]) q[++tail] = to,vis[to] = true;
}
}
if (d[T] == INF) break;
flow += minf[T]; cost += d[T] * minf[T];
u = T;
while (u != S){
ed[p[u]].f -= minf[T];
ed[p[u] ^ 1].f += minf[T];
u = ed[p[u] ^ 1].to;
}
}
return cost;
}
char ss[22][22],st[22][22],lim[22][22];
int n,m,id[22][22],X[8] = {0,0,-1,1,-1,-1,1,1},Y[8] = {-1,1,0,0,-1,1,-1,1},cnta,cntb;
int main(){
n = read(); m = read();
REP(i,n) REP(j,m) id[i][j] = (i - 1) * m + j;
REP(i,n) scanf("%s",ss[i] + 1);
REP(i,n) scanf("%s",st[i] + 1);
REP(i,n) scanf("%s",lim[i] + 1);
int E = n * m,x,nx,ny; S = 0; T = 3 * E + 1;
REP(i,n) REP(j,m){
x = lim[i][j] - '0';
if (ss[i][j] == '1' && st[i][j] == '0'){
cnta++;
build(S,id[i][j],1,0);
build(id[i][j] + E,id[i][j],x / 2,1);
build(id[i][j],id[i][j] + 2 * E,(x + 1) / 2,1);
}
else if (ss[i][j] == '0' && st[i][j] == '1'){
cntb++;
build(id[i][j],T,1,0);
build(id[i][j] + E,id[i][j],(x + 1) / 2,1);
build(id[i][j],id[i][j] + 2 * E,x / 2,1);
}
else {
build(id[i][j] + E,id[i][j],x / 2,1);
build(id[i][j],id[i][j] + 2 * E,x / 2,1);
}
for (int k = 0; k < 8; k++){
nx = i + X[k];
ny = j + Y[k];
if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
build(id[i][j] + 2 * E,id[nx][ny] + E,INF,0);
}
}
if (cnta != cntb) puts("-1");
else{
int ans = mincost();
Redge(S) if (ed[k].f){puts("-1"); return 0;}
printf("%d\n",ans / 2);
}
return 0;
}
