题目链接：UOJ 336
曾经有一款流行的游戏，叫做Infinity Loop，先来简单的介绍一下这个游戏：
游戏在一个 $n \times m$ 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在方格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的公共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 $15$ 种形状：
游戏开始时，棋盘中水管可能存在漏水的地方。
形式化地：如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。
玩家可以进行一种操作：选定一个含有非直线型水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 $90$ 度。
直线型水管是指左图里中间一行的两种水管。
现给出一个初始局面，请问最少进行多少次操作可以使棋盘上不存在漏水的地方。如果无法达成目标，输出 $-1$。
数据范围：$1 \le n \times m \le 2000$。
Solution
借鉴一下 Tiger0132 博客中的一句话：
判断网络流的一个办法：
- 网格图 / 棋盘 / 有规律的图案
- 有一些与暴力算法无关的奇怪性质
这道题：是棋盘；直管不能翻转。鉴定完毕。
于是我们考虑如何建模。
由于有旋转操作，于是我们把每个格子拆成 $4$ 个点，分别代表上下左右四个方向。又观察到是否漏水只和相邻两个格子有关，于是我们对棋盘进行黑白染色。黑点连向源点，白点连向汇点（注意这里的点是水管有接口的方向上的所有点），容量为 $1$，费用为 $0$。
我们把合法的接头数量看做是流量，将旋转次数看做是费用。如果最大流量等于要求的接头数量，那么最小费用就是最少的交换次数。
对于每个格子，我们用 $\text{U}, \text{R}, \text{D}, \text{L}$ 表示其拆点后的上、右、下、左四个点。对于格子 $(i, j)$，我们将 $\text{U}_{i, j}, \text{R}_{i, j}, \text{D}_{i, j}, \text{L}_{i, j}$ 分别和 $\text{D}_{i - 1, j}, \text{L}_{i, j + 1}, \text{U}_{i + 1, j}, \text{R}_{i, j - 1}$ 连一条容量为 $1$，费用为 $0$ 的边（注意连边方向是从源点向汇点）。
对于所有的水管形态，我们将它们分为本质不同的几种：
直管、十字
直管不能旋转，因此不需要考虑旋转导致的连边；十字旋转不会产生任何影响，因此也不需要额外连边。
单叉、直角、三叉
考虑一次旋转造成的影响：获得一个新的方向上的接口，同时失去一个方向上的接口。那么我们从被删除的方向上的点向获得的方向上的点连一条容量为 $1$，费用为旋转次数的边。
正确性
考虑证明这样连边的正确性。每个点向源汇点连边的容量均为 $1$，意味着只能旋转一次、并且代表一个接口数量。一个部分的点只会和另一个部分的唯一一个点匹配，正确性得证。
建好图之后直接跑最小费用最大流即可。
时间复杂度：$\mathcal O(n ^ 3 m ^ 3)$。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define U k + 0
#define R k + 1
#define D k + 2
#define L k + 3
#define E(x, y, c) addEdge(x, y, 1, c, opt)
const int N = 8e3 + 5, M = 1.5e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, maxFlow, minCost, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N];
bool vis[N];
void add(int u, int v, int w, int c) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addEdge(int u, int v, int w, int c, bool rev) {
if (rev) std::swap(u, v);
add(u, v, w, c), add(v, u, 0, -c);
}
bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memcpy(cur, lnk, sizeof(lnk));
std::queue<int> q;
q.push(s), dis[s] = 0, vis[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = false;
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (cap[i] && dis[v] > dis[u] + cost[i]) {
dis[v] = dis[u] + cost[i];
if (!vis[v]) q.push(v), vis[v] = true;
}
}
}
return dis[t] != INF;
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
vis[u] = true;
int ans = 0;
for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
int v = ter[i];
if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
int x = dfs(v, t, std::min(cap[i], flow - ans));
if (x) {
cap[i] -= x, cap[i ^ 1] += x;
ans += x, minCost += x * cost[i];
}
}
}
vis[u] = false;
return ans;
}
void mcmf(int s, int t) {
maxFlow = minCost = 0;
while (spfa(s, t)) {
int x;
while ((x = dfs(s, t, INF))) maxFlow += x;
}
}
int id(int i, int j) {
return ((i - 1) * m + j - 1) * 4 + 1;
}
int main() {
scanf("%d%d", &n, &m);
int s = 0, t = 4 * n * m + 1, cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x, k = id(i, j), opt = (i + j) & 1;
scanf("%d", &x);
if (i > 1) E(U, id(i - 1, j) + 2, 0);
if (j > 1) E(L, id(i, j - 1) + 1, 0);
if (x & 1) E(opt ? t : s, U, 0), cnt++;
if (x & 2) E(opt ? t : s, R, 0), cnt++;
if (x & 4) E(opt ? t : s, D, 0), cnt++;
if (x & 8) E(opt ? t : s, L, 0), cnt++;
switch(x) {
case 1: E(U, L, 1), E(U, D, 2), E(U, R, 1); break;
case 2: E(R, D, 1), E(R, L, 2), E(R, U, 1); break;
case 4: E(D, L, 1), E(D, U, 2), E(D, R, 1); break;
case 8: E(L, U, 1), E(L, R, 2), E(L, D, 1); break;
case 3: E(U, D, 1), E(R, L, 1); break;
case 6: E(R, L, 1), E(D, U, 1); break;
case 12: E(D, U, 1), E(L, R, 1); break;
case 9: E(L, R, 1), E(U, D, 1); break;
case 7: E(U, L, 1), E(R, L, 2), E(D, L, 1); break;
case 14: E(R, U, 1), E(D, U, 2), E(L, U, 1); break;
case 13: E(D, R, 1), E(L, R, 2), E(U, R, 1); break;
case 11: E(L, D, 1), E(U, D, 2), E(R, D, 1); break;
}
}
}
mcmf(s, t);
printf("%d\n", maxFlow << 1 == cnt ? minCost : -1);
return 0;
}
1 条评论
Orz!!!