Siyuan

「UOJ 336」无限之环
「UOJ 336」无限之环
扫描右侧二维码阅读全文
31
2019/03

「UOJ 336」无限之环

题目链接: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 条评论

  1. tiger0132

    Orz!!!

发表评论