Address
洛谷P3159
BZOJ2668
Solution
- 显然交换两个同色的棋子是不优的。
- 那么我们可以把黑棋看作空地，把交换相邻两个棋子看作：将一个白棋移动到相邻的某个空地中。
- 那么整个过程就可以看作：一开始棋盘上全是空地，然后我们在某些位置上放白棋，并进行一系列的移动。棋盘达到目标局面时，把棋盘上的白棋全部拿走。
- 考虑用费用流解决，先建立源点 \(S\) 和 汇点 \(T\)。
- 因为有交换次数的限制，所以把每个点 \(x\) 拆成 \(3\) 个点：\(in(x), out(x), mid(x)\)。
- 记 \(a[x]\) 表示 \(\lfloor\) 将相邻的白棋移到位置 \(x\) \(\rfloor\) 这一操作的次数。
- \(b[x]\) 表示 \(\lfloor\) 将位置 \(x\) 的白棋移到相邻位置 \(\rfloor\) 这一操作的次数。
- \(c[x]\) 表示 \(\lfloor\) 将相邻的白棋移到位置 \(x\) \(\rfloor\) 和 \(\lfloor\) 将位置 \(x\)的白棋移到相邻位置 \(\rfloor\) 这两个操作的次数之和的上限，也就是输入的第 \(3\) 个矩阵。
- 如果初始和目标局面中，\(x\) 均为白棋或均为空地，那么 \(a[x]=b[x]\)，所以 \(a[x],b[x]\) 的上限均为 \(\lfloor\frac{c[x]}{2}\rfloor\)。
- 如果 \(x\) 初始为白棋，目标为空地，那么 \(a[x]+1=b[x]\)，那么 \(a[x]\) 的上限是 \(\lfloor\frac{c[x]}{2}\rfloor\)，\(b[x]\) 的上限是 \(\lceil\frac{c[x]}{2}\rceil\)。
- 如果 \(x\) 初始为空地，目标为白棋，那么 \(b[x]+1=a[x]\)，那么 \(a[x]\) 的上限是 \(\lceil\frac{c[x]}{2}\rceil\)，\(b[x]\) 的上限是 \(\lfloor\frac{c[x]}{2}\rfloor\)。
- 然后连边 \((in(x),mid(x),a[x]的上限,0)，(mid(x),out(x),b[x]的上限,0)\)。
- 考虑源点和汇点的连边。
- 首先我们在某些位置上放白棋：假设在位置 \(x\) 放了 \(1\) 个白棋，那么连边：\((S,mid(x),1,0)\)。
- 同理，如果最后要在位置 \(x\) 拿走 \(1\) 个白棋，那么连边：\((mid(x),T,1,0)\)。
- 最后对于任意相邻两点 \(x,y\)，连边 \((out(x),in(y),∞,0)\)，表示白棋的转移。
- 求最小费用最大流就是答案。
- 注意特判无解：初始和目标局面白棋个数不同，或者最大流小于白棋个数。
Code
#include <bits/stdc++.h>
using namespace std;
const int e = 1e6 + 5, o = 1e3 + 5, dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
const int inf = 0x3f3f3f3f, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
bool vis[e];
int adj[e], nxt[e], pre[e], num = 1, go[e], n, m, s, t, nm, a[e], frm[e], c[e], f[e], d[e];
int ans, co[e], cs, ct, bs[o][o], bt[o][o], mxf;
inline void add(int x, int y, int v, int w)
{
nxt[++num] = adj[x]; frm[num] = x; adj[x] = num; go[num] = y; c[num] = v; co[num] = w;
nxt[++num] = adj[y]; frm[num] = y; adj[y] = num; go[num] = x; co[num] = -w;
}
inline bool bfs()
{
queue<int>q;
int i;
for (i = 1; i <= t; i++) d[i] = inf;
d[s] = pre[s] = 0; a[s] = inf;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for (i = adj[u]; i; i = nxt[i])
{
int v = go[i];
if (c[i] > f[i] && d[v] > d[u] + co[i])
{
d[v] = d[u] + co[i];
pre[v] = i;
a[v] = min(a[u], c[i] - f[i]);
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
if (d[t] == inf) return 0;
ans += d[t] * a[t];
mxf += a[t];
int u = t;
while (u != s)
{
f[pre[u]] += a[t];
f[pre[u] ^ 1] -= a[t];
u = frm[pre[u]];
}
return 1;
}
inline int in(int x, int y)
{
return (x - 1) * m + y;
}
inline int mid(int x, int y)
{
return (x - 1) * m + y + nm;
}
inline int out(int x, int y)
{
return (x - 1) * m + y + 2 * nm;
}
int main()
{
scanf("%d%d", &n, &m); nm = n * m; s = 3 * nm + 1; t = s + 1;
int i, j, x, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
char ch;
cin >> ch;
bs[i][j] = ch - '0';
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
char ch;
cin >> ch;
bt[i][j] = ch - '0';
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
char ch;
cin >> ch;
x = ch - '0';
if (bs[i][j]) add(s, mid(i, j), 1, 0), cs++;
if (bt[i][j]) add(mid(i, j), t, 1, 0), ct++;
if (bs[i][j] == bt[i][j])
{
add(in(i, j), mid(i, j), x / 2, 0);
add(mid(i, j), out(i, j), x / 2, 0);
}
else if (bs[i][j])
{
add(in(i, j), mid(i, j), x / 2, 0);
add(mid(i, j), out(i, j), (x + 1) / 2, 0);
}
else
{
add(in(i, j), mid(i, j), (x + 1) / 2, 0);
add(mid(i, j), out(i, j), x / 2, 0);
}
for (k = 0; k < 8; k++)
{
int x = dx[k] + i, y = dy[k] + j;
if (x < 1 || y < 1 || x > n || y > m) continue;
add(out(i, j), in(x, y), inf, 1);
}
}
if (cs != ct)
{
puts("-1");
return 0;
}
while (bfs());
if (mxf != ct) puts("-1");
else cout << ans << endl;
return 0;
}