建图拆点，最小费用最大流
题意：
分析：
首先我们认识到，对于我所在的棋盘，如果我把所有的黑子都摆放在指定的位置上了的话，那么白子也一定被摆在了指定的位置。
所以，这里我们不妨只看黑子，考虑让其摆放在规定的黑子位置上所消耗的步数最小。
不难想到，这是个匹配问题。我们要对所有的黑子对其归属位置进行匹配！
最小费用网络流的想法自然孕育而生。
但是还有一个问题：我们在匹配的过程中是否会影响到其他的匹配呢？
即，黑子在不断进行交换移动中会不会对其他的黑子造成影响，使其交换次数发生改变。
这也是我非常不解的地方。想了很久没有想明白。上网搜题解大多也对这一点没有解释。直到我看到了洛谷的一篇题解，
有这样的一段话：
任何两个棋子在交换过程中路径一定不会相交，因为相交的话肯定可以交换两个棋子的后半段路径使得不相交。
醍醐灌顶！！
真的是精彩！！！
如下图：
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;
}精妙绝伦！！！
京公网安备 11010502036488号