[CQOI2012]交换棋子

https://ac.nowcoder.com/acm/problem/19921

建图拆点，最小费用最大流

题意：

图片说明

分析：

首先我们认识到，对于我所在的棋盘，如果我把所有的黑子都摆放在指定的位置上了的话，那么白子也一定被摆在了指定的位置。
所以，这里我们不妨只看黑子，考虑让其摆放在规定的黑子位置上所消耗的步数最小。

不难想到，这是个匹配问题。我们要对所有的黑子对其归属位置进行匹配！

最小费用网络流的想法自然孕育而生。
但是还有一个问题：我们在匹配的过程中是否会影响到其他的匹配呢？
即，黑子在不断进行交换移动中会不会对其他的黑子造成影响，使其交换次数发生改变。

这也是我非常不解的地方。想了很久没有想明白。上网搜题解大多也对这一点没有解释。直到我看到了洛谷的一篇题解，
有这样的一段话：
任何两个棋子在交换过程中路径一定不会相交，因为相交的话肯定可以交换两个棋子的后半段路径使得不相交。
醍醐灌顶！！
真的是精彩！！！

如下图：
图片说明
1号棋子目标为X1，2号棋子目标为X2，我们可以发现他们马上就会向撞了。这会造成部署的增加！！
但此时2号棋子可以变为1号棋子，1号棋子可以变为2号棋子
如图：

交换时不会有什么问题的！！如果你对此抱有疑问那么我想请你看看白书中的一道水题(挑战程序设计竞赛)
POJ 1852
https://vjudge.net/problem/POJ-1852

此题中他忽略了蚂蚁们的不同，其实就是和我们这道题一样啊！！！！(自以为自己会了，但还没有真正的搞懂啊！！)
分割线 ———————————————————————————————— 分割线
如此，我们确定了，这是一个匹配的最小费用最大流问题！

那么，我们关心该如何建图了，这里面也有难点的！
自然我们要这样做：
1.首先，相邻各自之间连边。cap = inf,cost=1
2.将原本便存在黑子的格子和s相连(由s指向格点),cap = 1,cost = 0
3.将规定中放置黑子的格子和t相连(格点指向t)，cao = 1,cost = 0
那么关键来了：
我们如何保证每个格点只被交换mij呢？
这还不简单！只需拆一个点就好了嘛！！很常规。
但是，这道题的特别之处在于：
在从a[i][j]交换到a[k][h]时你会发现除了a[i][j]和a[k][h]这两个格点，其余的所有格点其实都被走了交换了两次
比如 a b c 我在a要到c去
我先跳进b a点交换一次，b点交换一次
我在跳出b跳进c b点交换一次，c点交换一次
总共a，c两点交换1次，b点交换2次。

落实在我们所构建的图中便是：
对于与s所连接的初始格点他们的第一步占流为1
对于与t所连接的终止格点他们最后一步占流为1
其余占流全部为2

大麻烦了！！注意这可是占流是cap而并非是cost。

如何解决呢？这里我们这样解决的：将流量/2 再分给一条路，让路径同时经过这两条路，等同于消耗掉2流
如图：
图片说明
如此，我们就可以实现一次耗费2单位流。
而s和t的情况直接连接mid就好了，其余的节点之间以out连in相互连接

那么，如果cap的值是奇数的时候怎么办呢？
我们知道不与s和t连接的格点他们的交换次数是以2为单位减少的，那么对于他们来说，奇偶就无关了！

而对于s和t你画图看看就会发现：
s与mid连接从out出来mid->out多走了一次
in经过mid到达t in->mid多走了一次
图片说明
那么我们就判断如果此格点和s连接了，那么多出来的那1单位流量就给mid->out
如果此格点和t连接了，那么多出来的1单位流就给in->mid
此外，倘若既与s连接了又与t连接了，那么这1单位流添不添加就没有什么意义了，两边直接cap/2吧。

如此我们的图建完了，直接跑个最小流算法。注意在此之前判断一下两期盼黑子数目是否相同。

代码如下：

#include<iostream>
#include<string>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int inf = 2e9;
const int max_n = 800;
const int max_m = max_n * max_n;
int n, m;
struct edge
{
    int to, cap, rev, cost, next;
}E[max_m * 4];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap, int cost) {
    E[cnt].to = to;E[cnt].cap = cap;
    E[cnt].cost = cost;E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];head[from] = cnt++;

    E[cnt].to = from;E[cnt].cap = 0;
    E[cnt].cost = -cost;E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];head[to] = cnt++;
}

int dist[max_n];
bool used[max_n];
pii fa[max_n];
bool spfa(int s, int t) {
    fill(dist, dist + max_n, inf);
    fill(used, used + max_n, false);
    dist[s] = 0;used[s] = true;
    queue<int> que;que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        used[u] = false;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (e.cap <= 0 || dist[e.to] <= dist[u] + e.cost)continue;
            dist[e.to] = dist[u] + e.cost;
            fa[e.to] = { u,i };
            if (used[e.to]) continue;
            que.push(e.to);
            used[e.to] = true;
        }
    }return dist[t] != inf;
}
int matchpath(int s, int t, int& f) {
    int d = f;int res = 0;
    for (int cur = t;cur != s;cur = fa[cur].first) {
        edge& e = E[fa[cur].second];
        d = min(d, e.cap);
    }
    f -= d;res += d * dist[t];
    for (int cur = t;cur != s;cur = fa[cur].first) {
        edge& e = E[fa[cur].second];
        e.cap -= d;E[e.rev].cap += d;
    }
    return res;
}
int mcf(int s, int t, int f) {
    int res = 0;int cost = 0;
    while (f > 0 && spfa(s, t)) {
        cost = matchpath(s, t, f);
        res += cost;
    }return f > 0 ? -1 : res;
}
void init() {
    fill(head, head + max_n, false);
    cnt = 1;
}
string ch1[max_n];
string ch2[max_n];
string ch3[max_n];

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    int start = n * m * 3 + 1;
    int ed = start + 1;
    int flowl = 0, flowr = 0;
    for (int i = 1;i <= n;i++)
        cin >> ch1[i], ch1[i] = "0" + ch1[i];
    for (int i = 1;i <= n;i++)
        cin >> ch2[i], ch2[i] = "0" + ch2[i];
    for (int i = 1;i <= n;i++)
        cin >> ch3[i], ch3[i] = "0" + ch3[i];
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            flowl += (ch1[i][j] == '1');
            flowr += (ch2[i][j] == '1');
            int mid = (i - 1) * m + j;
            int inn = mid + n * m;
            int out = inn + n * m;
            int cap = ch3[i][j] - '0';
            if (ch1[i][j] == '1' && ch2[i][j] == '1')
                add(inn, mid, cap >> 1, 1), add(mid, out, cap >> 1, 1);
            else if (ch1[i][j] == '1')
                add(inn, mid, cap >> 1, 1), add(mid, out, (cap + 1) >> 1, 1);
            else if (ch2[i][j] == '1')
                add(inn, mid, (cap + 1) >> 1, 1), add(mid, out, cap >> 1, 1);
            else
                add(inn, mid, cap >> 1, 1), add(mid, out, cap >> 1, 1);
            if (ch1[i][j] == '1')add(start, mid, 1, 0);
            if (ch2[i][j] == '1')add(mid, ed, 1, 0);
            for (int k = 0;k <= 1;k++) {
                for (int h = -1;h <= 1;h++) {
                    if (k == 0 && (h == 0 || h == -1))continue;
                    int ii = i + k;int jj = j + h;
                    if (ii > n || ii <= 0 || jj > m || jj <= 0)continue;
                    int innr = (ii - 1) * m + jj + n * m;
                    int outr = innr + n * m;
                    add(out, innr, inf, 0);
                    add(outr, inn, inf, 0);
                }
            }
        }
    }if (flowl != flowr)cout << -1 << endl;
    else cout << mcf(start, ed, flowl) / 2 << endl;
}

精妙绝伦！！！