BZOJ 3144 [HNOI2013] 切糕：三維最小割建模詳解

問題描述

有一塊尺寸 P×Q×R 的切糕（三維網格），每個單元格 (x,y,z) 有一個不和諧值 v(x,y,z)。需要從底面（z=1）到頂面（z=R+1）切一刀，形成一個切面 f(x,y) 表示每列切到的高度。要求：

1. 切面高度單調：|f(x,y) - f(x',y')| ≤ D 對於相鄰的 (x,y) 和 (x',y')（上下左右四向）。
2. 最小化切面經過的所有單元格的不和諧值總和。

關鍵建模：最小割 = 最小切面代價

經典技巧：將「選擇切面高度」轉化為「割斷邊」。

分層圖構建

• 每個 (x,y) 列拆分為 R+1 層節點，第 k 層代表「切面高度 ≥ k」。
• 第 k 層向第 k+1 層連邊，容量 = v(x,y,k)（切在這層的代價）。
• 源點 S 連向所有 (x,y,1)，汇點 T 從所有 (x,y,R+1) 連入，容量 = INF（強制切面貫穿整個高度）。

相鄰高度差限制（核心難點）

要求 |f(x,y) - f(nx,ny)| ≤ D。等價於：若某列切到高度 k，則相鄰列必須至少切到高度 k-D。
在圖中體現為：從 (x,y,k) 向相鄰列的 (nx,ny,k-D) 連容量 INF 的邊（k > D 時）。
若割集切斷了 (x,y,k)→(x,y,k+1)（即選擇高度 k），則為了不切斷 INF 邊，相鄰列的 (nx,ny,k-D)→(nx,ny,k-D+1) 必須也被切斷（即高度 ≥ k-D）。雙向連邊即雙向限制。

Dinic 最大流/最小割實現

#include 
using namespace std;
const int INF = 1e9;
const int MAXN = 45*45*45 + 5;  // P,Q,R ≤ 40
const int MAXM = 2000000;

struct Edge { int to, nxt, cap; } e[MAXM];
int head[MAXN], cur[MAXN], dep[MAXN], ecnt = 1;
int P, Q, R, D, S, T;

void addEdge(int u, int v, int c) {
    e[++ecnt] = {v, head[u], c}; head[u] = ecnt;
    e[++ecnt] = {u, head[v], 0}; head[v] = ecnt;
}

bool bfs() {
    memset(dep, -1, sizeof(dep));
    queue q; q.push(S); dep[S] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
            if (e[i].cap && dep[e[i].to] == -1)
                dep[e[i].to] = dep[u] + 1, q.push(e[i].to);
    }
    return dep[T] != -1;
}

int dfs(int u, int f) {
    if (u == T) return f;
    int sum = 0;
    for (int &i = cur[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (e[i].cap && dep[v] == dep[u] + 1) {
            int ret = dfs(v, min(f - sum, e[i].cap));
            e[i].cap -= ret; e[i^1].cap += ret;
            sum += ret;
            if (sum == f) return sum;
        }
    }
    if (!sum) dep[u] = -1;
    return sum;
}

int id(int x, int y, int z) {  // z: 1..R+1
    return (z-1)*P*Q + (x-1)*Q + y;
}

int main() {
    scanf("%d%d%d%d", &P, &Q, &R, &D);
    static int v[45][45][45];
    for (int k = 1; k <= R; ++k)
        for (int i = 1; i <= P; ++i)
            for (int j = 1; j <= Q; ++j)
                scanf("%d", &v[i][j][k]);

    S = 0; T = P*Q*(R+1) + 1;
    int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};

    for (int i = 1; i <= P; ++i)
        for (int j = 1; j <= Q; ++j) {
            addEdge(S, id(i,j,1), INF);
            addEdge(id(i,j,R+1), T, INF);
            for (int k = 1; k <= R; ++k) {
                addEdge(id(i,j,k), id(i,j,k+1), v[i][j][k]);
                if (k > D) {
                    for (int d = 0; d < 4; ++d) {
                        int ni = i + dx[d], nj = j + dy[d];
                        if (ni<1 || ni>P || nj<1 || nj>Q) continue;
                        addEdge(id(i,j,k), id(ni,nj,k-D), INF);
                    }
                }
            }
        }

    long long ans = 0;
    while (bfs()) {
        memcpy(cur, head, sizeof(head));
        ans += dfs(S, INF);
    }
    printf("%lld\n", ans);
    return 0;
}

複雜度分析

• 節點數：P×Q×(R+1) ≤ 40×40×41 ≈ 6.5萬
• 邊數：每列 R 條豎向邊 + 相鄰列 4×(R-D) 條橫向邊，總計 ~百萬級。
• Dinic 在此類層次圖上極快，實際運行毫秒級。