题目链接

BZOJ2668

题解

容易想到由\(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;

}