神奇的建模。。。原题链接
如果你真的把交换看成交换，就\(GG\)了。首先我们要把交换看成是白棋的移动。
然后，很容易的就想到建模的大致思路：建立超级源点S和超级汇点T，从S向初始局面每个白棋所在的格子连边，从目标局面每个白棋所在的格子向T连边，在相邻的格子中间加一些有限制的边，跑一波费用流。
那中间的那些边应该怎么加呢，先考虑把每个格子拆成两个点，中间连一条以交换次数为流量上限的边。但是这样会有问题，考虑某个白棋移动路径上的点，其实只有开头的格子交换了一次，中间的都是两次。只拆两个体现不了在中间或首尾的差别，那我们就拆三个。
把一个格子拆成三个点：TYPE1，TYPE2，TYPE3，分别表示流入，当前格子，流出。与S和T的连边改为向TYPE2连边，与相邻格子的连边在TYPE1与TYPE3之间连，另外从TYPE2向TYPE1和TYPE3连边，这样就能体现在路径上位置的差别了。
那这些边的容量和费用该怎么设置呢？
1.TYPE1与TYPE3之间的连边容量为\(INF\)，费用为\(1\)。
2.S与TYPE2，TYPE2与T容量为\(1\)，费用为\(0\)。
3.TYPE2与TYPE1和TYPE3的连边（重点）：
对于某个格子（假设它的交换上限为\(w\)，"/"号代表整除）：
①若初始为白棋，目标为黑棋，则从TYPE1向TYPE2连一条容量为\(w/2\)，费用为\(0\)的边，从TYPE2向TYPE3连一条容量为\((w+1)/2\)，费用为\(0\)的边
②若初始为黑棋，目标为白棋，则从TYPE1向TYPE2连一条容量为\((w+1)/2\)，费用为\(0\)的边，从TYPE2向TYPE3连一条容量为\(w/2\)，费用为\(0\)的边
③若始末颜色相同，则从TYPE1向TYPE2连一条容量为\(w/2\)，费用为\(0\)的边，从TYPE2向TYPE3连一条容量为\(w/2\)，费用为\(0\)的边
为什么权值要这样设，因为我们要保持收支平衡，使得每个格子在交换之后的颜色是对的。还有我们考虑的是白棋的移动，因此①应该会多一次流出，于是我们尽量把零头分给TYPE2与TYPE3之间的那条边。②同理。
注意判\(-1\)！
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define N 10000
#define INF 0x3f3f3f3f
int n, m, S, T;
struct MCMF
{
struct Edge
{
int from, to, cap, flow, cost;
};
int S, T;
int d[N+5], a[N+5], vis[N+5], pre[N+5];
vector<int> G[N+5];
vector<Edge> edges;
void init(int S, int T)
{
this->S = S, this->T = T;
}
void addEdge(int from, int to, int cap, int cost)
{
edges.pb(Edge{from, to, cap, 0, cost}), edges.pb(Edge{to, from, 0, 0, -cost});
G[from].pb(edges.size()-2), G[to].pb(edges.size()-1);
}
int SPFA(int &flow, int &cost)
{
memset(d, 0x3f, sizeof d), memset(vis, 0, sizeof vis);
d[S] = 0, a[S] = INF, vis[S] = 1, pre[S] = 0;
queue<int> q;
q.push(S);
while(!q.empty())
{
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = 0; i < G[u].size(); ++i)
{
Edge &e = edges[G[u][i]];
if(e.cap > e.flow && d[e.to] > d[u]+e.cost)
{
d[e.to] = d[u]+e.cost;
pre[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap-e.flow);
if(!vis[e.to]) vis[e.to] = 1, q.push(e.to);
}
}
}
if(d[T] == INF) return 0;
int u = T;
flow += a[T], cost += d[T]*a[T];
while(u != S)
{
edges[pre[u]].flow += a[T], edges[pre[u]^1].flow -= a[T];
u = edges[pre[u]].from;
}
return 1;
}
pii minCost()
{
int flow = 0, cost = 0;
while(SPFA(flow, cost));
return mp(flow, cost);
}
}solver;
int Val(char c)
{
return c-'0';
}
int TYPE1(int i, int j)
{
return ((i-1)*m+j)*3-2;
}
int TYPE2(int i, int j)
{
return ((i-1)*m+j)*3-1;
}
int TYPE3(int i, int j)
{
return ((i-1)*m+j)*3;
}
int a[25][25], b[25][25], w[25][25];
int d[8][2] = {-1,0,1,0,0,-1,0,1,-1,-1,-1,1,1,-1,1,1};
//0:black 1:white
int main()
{
scanf("%d%d", &n, &m);
S = 0, T = 3*n*m+1;
solver.init(S, T);
char c;
int sum = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) cin >> c, a[i][j] = Val(c), sum += a[i][j];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) cin >> c, b[i][j] = Val(c);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) cin >> c, w[i][j] = Val(c);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(a[i][j]) solver.addEdge(S, TYPE2(i, j), 1, 0);
if(b[i][j]) solver.addEdge(TYPE2(i, j), T, 1, 0);
if(a[i][j] == 0 && b[i][j] == 1)
solver.addEdge(TYPE1(i, j), TYPE2(i, j), (w[i][j]+1)/2, 0), solver.addEdge(TYPE2(i, j), TYPE3(i, j), w[i][j]/2, 0);
else if(a[i][j] == 1 && b[i][j] == 0)
solver.addEdge(TYPE1(i, j), TYPE2(i, j), w[i][j]/2, 0), solver.addEdge(TYPE2(i, j), TYPE3(i, j), (w[i][j]+1)/2, 0);
else
solver.addEdge(TYPE1(i, j), TYPE2(i, j), w[i][j]/2, 0), solver.addEdge(TYPE2(i, j), TYPE3(i, j), w[i][j]/2, 0);
for(int k = 0, ti, tj; k < 8; ++k)
{
ti = i+d[k][0], tj = j+d[k][1];
if(ti < 1 || ti > n || tj < 1 || tj > m) continue;
solver.addEdge(TYPE3(i, j), TYPE1(ti, tj), INF, 1);
}
}
pii res = solver.minCost();
if(res.first != sum) printf("-1\n");
else printf("%d\n", res.second);
return 0;
}