有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。
Solution
一个点拆三份，入点，主点，出点
入点向主点连边，主点向出点连边，设该点允许的交换次数为 (x) ，根据以下规则确定
-
若为初态点，则入边限流 (x/2)，出边限流 ((x+1)/2)
-
若为末态点，则入边限流 ((x+1)/2)，出边限流 (x/2)
-
否则，入边限流 (x/2)，出边限流 ((x+1)/2)
(S o) 初态点，末态点 ( o T)，容量 (1)，费用 (0)
八连通相互连边，容量 (infty)，费用 (1)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define reset(x) memset(x,0,sizeof x)
#define reset3f(x) memset(x,0x3f,sizeof x)
const int N = 1005;
namespace flow {
const int N = 100005;
const int M = 1000005;
const int inf = 1e+12;
struct Edge {
int p, c, w, nxt = -1;
} e[N];
int s, t, tans, ans, cost, ind, bus[N], qhead = 0, qtail = -1, qu[M],vis[N], dist[N];
void graph_link(int p, int q, int c, int w) {
e[ind].p = q;
e[ind].c = c;
e[ind].w = w;
e[ind].nxt = bus[p];
bus[p] = ind;
++ind;
}
void make(int p, int q, int c, int w) {
graph_link(p, q, c, w);
graph_link(q, p, 0, -w);
}
int dinic_spfa() {
qhead = 0;
qtail = -1;
memset(vis, 0x00, sizeof vis);
memset(dist, 0x3f, sizeof dist);
vis[s] = 1;
dist[s] = 0;
qu[++qtail] = s;
while (qtail >= qhead) {
int p = qu[qhead++];
vis[p] = 0;
for (int i = bus[p]; i != -1; i = e[i].nxt)
if (dist[e[i].p] > dist[p] + e[i].w && e[i].c > 0) {
dist[e[i].p] = dist[p] + e[i].w;
if (vis[e[i].p] == 0)
vis[e[i].p] = 1, qu[++qtail] = e[i].p;
}
}
return dist[t] < inf;
}
int dinic_dfs(int p, int lim) {
if (p == t)
return lim;
vis[p] = 1;
int ret = 0;
for (int i = bus[p]; i != -1; i = e[i].nxt) {
int q = e[i].p;
if (e[i].c > 0 && dist[q] == dist[p] + e[i].w && vis[q] == 0) {
int res = dinic_dfs(q, min(lim, e[i].c));
cost += res * e[i].w;
e[i].c -= res;
e[i ^ 1].c += res;
ret += res;
lim -= res;
if (lim == 0)
break;
}
}
return ret;
}
void solve(int _s,int _t) {
s=_s; t=_t;
while (dinic_spfa()) {
memset(vis, 0x00, sizeof vis);
ans += dinic_dfs(s, inf);
}
}
void init() {
memset(bus, 0xff, sizeof bus);
}
}
int n,m;
char a[N][N],b[N][N],c[N][N];
int idIn(int i,int j) {
return i*m-m+j+2;
}
int idMid(int i,int j) {
return 2ll + n*m + i*m-m+j;
}
int idOut(int i,int j) {
return 2ll + 2*n*m + i*m-m+j;
}
int check(int i,int j) {
if(i && j && i<=n && j<=m) return 1;
return 0;
}
signed main() {
flow::init();
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i]+1;
for(int i=1;i<=n;i++) cin>>b[i]+1;
for(int i=1;i<=n;i++) cin>>c[i]+1;
int cnt=0,tot=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(a[i][j]=='1') cnt++;
if(b[i][j]=='1') tot++;
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(a[i][j]=='1') flow::make(1,idMid(i,j),1,0);
if(b[i][j]=='1') flow::make(idMid(i,j),2,1,0);
int x=c[i][j]-'0';
if(a[i][j]=='1' && b[i][j]=='0') {
flow::make(idIn(i,j),idMid(i,j),x/2,0);
flow::make(idMid(i,j),idOut(i,j),(x+1)/2,0);
}
else if(a[i][j]=='0' && b[i][j]=='1') {
flow::make(idIn(i,j),idMid(i,j),(x+1)/2,0);
flow::make(idMid(i,j),idOut(i,j),x/2,0);
}
else {
flow::make(idIn(i,j),idMid(i,j),x/2,0);
flow::make(idMid(i,j),idOut(i,j),(x+1)/2,0);
}
for(int k=i-1;k<=i+1;k++) {
for(int l=j-1;l<=j+1;l++) {
if(i!=k || j!=l) {
if(check(k,l)) flow::make(idOut(i,j),idIn(k,l),99,1);
}
}
}
}
}
flow::solve(1,2);
if(flow::ans==cnt && cnt==tot) cout<<flow::cost;
else cout<<-1;
}