题目地址：洛谷：【P3227】[HNOI2013]切糕 – 洛谷、BZOJ：Problem 3144. — [Hnoi2013]切糕

题目描述

经过千辛万苦小 A 得到了一块切糕，切糕的形状是长方体，小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑，小 A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。
出于简便考虑，我们将切糕视作一个长 P、宽 Q、高 R 的长方体点阵。我们将位于第 z层中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z)，它有一个非负的不和谐值 v(x,y,z)。一个合法的切面满足以下两个条件：

1. 与每个纵轴(一共有 P*Q 个纵轴)有且仅有一个交点。即切面是一个函数 f(x,y)，对于所有 1≤x≤P, 1≤y≤Q,我们需指定一个切割点 f(x,y),且 1≤f(x,y)≤R。
2. 切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的 1≤x,x’≤P 和 1≤y,y’≤Q，若|x-x’|+|y-y’|=1，则|f(x,y)-f(x’,y’)| ≤D，其中 D 是给定的一个非负整数。 可能有许多切面f 满足上面的条件，小A 希望找出总的切割点上的不和谐值最小的那个。

输入输出格式

输入格式：
第一行是三个正整数P,Q,R，表示切糕的长P、 宽Q、高R。第二行有一个非负整数D，表示光滑性要求。接下来是R个P行Q列的矩阵，第z个 矩阵的第x行第y列是v(x,y,z) (1<=x<=P, 1<=y<=Q, 1<=z<=R)。
100%的数据满足P,Q,R<=40，0<=D<=R，且给出的所有的不和谐值不超过1000。

输出格式：
仅包含一个整数，表示在合法基础上最小的总不和谐值。

输入输出样例

输入样例#1：

2 2 2
1
6 1
6 1
2 6
2 6

输出样例#1：

6

说明

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

题解

网络流中，表示“选择”含义我们通常使用最小割模型。本题中，我们想从某个纵轴(x, y)的若干点中选取一个，这种情况我们可以采取用点权作为容量的边将点连成一条链，再分别从链头链尾向源汇连不可割（容量无限）的边，这样割去某个边就可以代表选择某个点了。
然后，我们还需要加入限制|f(x,y)-f(x',y')| \leq D。其实就是说，对于每个点，当相邻纵轴选取的点的距离超过D，就得让这种方案无效，即仍然有流可以通过这一部分到达汇，可以通过加边的方法实现。对于任意点 (x, y, z) ，向相邻点 (x', y', z - D) 连容量无限的边，这样就可以满足限制条件了。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                flow += d; left -= d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(!left) return flow;
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

const int fix[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};

int n, m, h, d, v[45][45][45], S, T;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); h = readint(); d = readint();
    S = n * m * (h + 1) + 1; T = S + 1;
    for(int k = 1; k <= h; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                v[i][j][k] = readint();
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int p = (i - 1) * m + j;
            addedge(S, p, INF);
            addedge(h * n * m + p, T, INF);
            for(int k = 1; k <= h; k++) {
                addedge((k - 1) * n * m + p, k * n * m + p, v[i][j][k]);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int t = 0; t < 4; t++) {
                int nx = i + fix[0][t], ny = j + fix[1][t];
                if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                for(int k = d + 1; k <= h + 1; k++) {
                    addedge((k - 1) * n * m + (i - 1) * m + j, 
                        (k - d - 1) * n * m + (nx - 1) * m + ny, INF);
                }
            }
        }
    }
    printf("%d", dinic(S, T));
    return 0;
}