Description

经过千辛万苦小 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 \times Q\) 个纵轴) 有且仅有一个交点. 即切面是一个函数 \(f(x, y)\), 对于所有 \(1 \leq x \leq P, 1 \leq y \leq Q\), 我们需指定一个切割点 \(f(x, y)\), 且 \(1 \leq f(x, y) \leq Q\).
  2. 切面需要满足一定的光滑性要求, 即相邻纵轴上的切割点不能相距太远. 对于所有的 \(1 \leq x, x' \leq P\) 和 \(1 \leq y, y' \leq Q\), 若 \(|x - x'| + |y - y'| = 1\), 则 \(|f(x, y) - f(x', y')| \leq D\), 其中 \(D\) 时给定的一个非负整数.

可能有许多切面 \(f\) 满足上面的条件, 小 A 希望找出总的切割点上的不和谐值最小的那个, 即 \(\sum_{x,y} v(x, y, f(x, y))\) 最小.

Input

第一行是三个正整数 \(P, Q, R\), 表示切糕的长 \(P\)、宽 \(Q\)、高 \(R\). 第二行有一个非负 整数 \(D\), 表示光滑性要求.

接下来是 \(R\) 个 \(P\) 行 \(Q\) 列的矩阵, 第 \(z\) 个矩阵的第 \(x\) 行第 \(y\) 列是 \(v(x, y, z)\) (\(1 \leq x \leq P, 1 \leq y \leq Q, 1 \leq z \leq R\)) .

Output

仅包含一个整数, 表示在合法基础上最小的总不和谐值.

Sample Input

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

Sample Output

6

Data Range

对于 100% 的数据, 满足:\(P, Q, R \leq 40, 0 \leq D \leq R\), 且给出的所有的不和谐值不超过 \(1000\).

Explanation

相邻等高两个位置之间是可以进行割的操作的, 代价为不和谐值.

在可允许的高度差之间, 可以连一条不可以割断的边.

最后将每一纵列的最高处和汇连一条边, 然后跑一个最小割.

明显把切糕切成两半就是最小割水题对吧......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 100100, maxm = 1001000, maxN = 50;
const int infinit = 0x3fffffff;

const int movx[4] = { 0,  0, 1, -1 },
          movy[4] = { 1, -1, 0,  0 };

class Dinic
{
public:
    struct edge
    {
        int u, v, flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, int flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        queue<int> que;
        memset(level, 0, sizeof(level));
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] > 0)
            return true;
        return false;
    }
    int find(int p, int mn)
    {
        if (p == t)
            return mn;
        int sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = find(ep->v, min(ep->flow, mn - sum));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    int eval(void)
    {
        int sum = 0, tmp;
        while (make_level()) {
            tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int P, Q, R, D;
int f[maxN][maxN][maxN];
inline int pos(int x, int y, int z) {
    if (z == 0) return 0;
    return (z-1)*P*Q + (x-1)*Q + y; }

int main(int argc, char** argv)
{
    // The cake is a lie.
    scanf("%d%d%d%d", &P, &Q, &R, &D);
    rep(k, 1, R) rep(i, 1, P) rep(j, 1, Q)
        scanf("%d", &f[i][j][k]);
    // Aperture Science reassure you that you will be baked, and there
    // will be cake.
    graph.s = 0;
    graph.t = P * Q * R + 1;
    graph.n = graph.t + 1;
    rep(i, 1, P) rep(j, 1, Q) {
        rep(k, 1, R) {
            graph.add_edge(pos(i, j, k-1), pos(i, j, k), f[i][j][k]);
            if (k > D) rep(mv, 0, 3) {
                int nx = i + movx[mv], ny = j + movy[mv];
                if (nx < 1 || nx > P || ny < 1 || ny > Q)
                    continue;
                graph.add_edge(pos(i, j, k), pos(nx, ny, k-D), infinit);
            }
        }
        graph.add_edge(pos(i, j, R), graph.t, infinit);
    }
    // What are you doing? Come back!
    int res = graph.eval();
    printf("%d\n", res);
    return 0;
}