传送门
好难的网络流啊，建图真的超难。
如果不告诉我是网络流的话，我估计就会写dfs了。
使用费用流解决本题，设点 $p[i][j]$ 的参与交换的次数上限为 $v[i][j]$ ，以下为建图方式：
-
将一个点分成三个点，分别为入点，原点和出点。
-
如果开始的图上该位置有棋子，那么从S到该点的原点连一条边权1，费用0的边
-
如果结束的图上该位置有棋子，那么从该点的原点到T连一条边权1，费用0的边
-
如果该点只在开始的图上出现，那么从该点的入点向原点连一条边权为 $v[i][j]/2$ ，费用为1的边，从该点的原点向出点连一条边权为 $(v[i][j]+1)/2$ ，费用为0的边
-
如果该点只在结束的图上出现，那么从该点的入点向原点连一条边权为 $(v[i][j]+1)/2$ ，费用为1的边，从该点的原点向出点连一条边权为 $v[i][j]/2$ ，费用为0的边
-
如果以上两点都不符合，那么从该点的入点向原点连一条边权为 $v[i][j]/2$ ，费用为1的边，从该点的原点向出点连一条边权为 $v[i][j]/2$ ，费用为0的边
——by zhouyonglong
我只是题解的搬运工。
最后把每个点的原点和它相邻的点的原点连一条容量为INF，费用为0的边
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000001
#define id(i, j, k) ((i - 1) * m + j + (k - 1) * n * m)
using namespace std;
int n, m, cnt, s, t, ans, sum1, sum2, sum;
int head[N], to[N], nex[N], val[N], cost[N], dis[N], pre[N], path[N];
char s1[21][21], s2[21][21], c[21][21];
const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
bool vis[N];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
inline void add(int x, int y, int z, int v)
{
to[cnt] = y;
val[cnt] = z;
cost[cnt] = v;
nex[cnt] = head[x];
head[x] = cnt++;
}
inline bool spfa()
{
int i, u, v;
queue <int> q;
memset(vis, 0, sizeof(vis));
memset(pre, -1, sizeof(pre));
memset(dis, 127, sizeof(dis));
q.push(s);
dis[s] = 0;
while(!q.empty())
{
u = q.front();
vis[u] = 0;
q.pop();
for(i = head[u]; ~i; i = nex[i])
{
v = to[i];
if(val[i] && dis[v] > dis[u] + cost[i])
{
dis[v] = dis[u] + cost[i];
pre[v] = u;
path[v] = i;
if(!vis[v])
{
q.push(v);
vis[v] = 1;
}
}
}
}
return pre[t] != -1;
}
inline void E()
{
puts("-1"), exit(0);
}
int main()
{
int i, j, k, x, y, f;
n = read();
m = read();
s = 0, t = 3 * n * m + 1;
memset(head, -1, sizeof(head));
for(i = 1; i <= n; i++) scanf("%s", s1[i] + 1);
for(i = 1; i <= n; i++) scanf("%s", s2[i] + 1);
for(i = 1; i <= n; i++) scanf("%s", c[i] + 1);
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
c[i][j] -= '0';
if(s1[i][j] == '1')
{
sum1++;
add(s, id(i, j, 2), 1, 0);
add(id(i, j, 2), s, 0, 0);
}
if(s2[i][j] == '1')
{
sum2++;
add(id(i, j, 2), t, 1, 0);
add(t, id(i, j, 2), 0, 0);
}
if(s1[i][j] == '1' && s2[i][j] == '0')
{
add(id(i, j, 1), id(i, j, 2), c[i][j] / 2, 1);
add(id(i, j, 2), id(i, j, 1), 0, -1);
add(id(i, j, 2), id(i, j, 3), (c[i][j] + 1) / 2, 0);
add(id(i, j, 3), id(i, j, 2), 0, 0);
}
if(s1[i][j] == '0' && s2[i][j] == '1')
{
add(id(i, j, 1), id(i, j, 2), (c[i][j] + 1) / 2, 1);
add(id(i, j, 2), id(i, j, 1), 0, -1);
add(id(i, j, 2), id(i, j, 3), c[i][j] / 2, 0);
add(id(i, j, 3), id(i, j, 2), 0, 0);
}
if(s1[i][j] == s2[i][j])
{
add(id(i, j, 1), id(i, j, 2), c[i][j] / 2, 1);
add(id(i, j, 2), id(i, j, 1), 0, -1);
add(id(i, j, 2), id(i, j, 3), c[i][j] / 2, 0);
add(id(i, j, 3), id(i, j, 2), 0, 0);
}
for(k = 0; k < 8; k++)
{
x = i + dx[k];
y = j + dy[k];
if(1 <= x && x <= n && 1 <= y && y <= m)
{
add(id(i, j, 3), id(x, y, 1), 1e9, 0);
add(id(x, y, 1), id(i, j, 3), 0, 0);
}
}
}
if(sum1 != sum2) E();
while(spfa())
{
f = 1e9;
for(i = t; i != s; i = pre[i]) f = min(f, val[path[i]]);
sum += f;
ans += dis[t];
for(i = t; i != s; i = pre[i])
{
val[path[i]] -= f;
val[path[i] ^ 1] += f;
}
}
if(sum != sum1) E();
printf("%d\n", ans);
return 0;
}