OI

BZOJ 3144: [Hnoi2013]切糕

Description

Input

第一行是三个正整数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。

Output

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

Sample Input

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

Sample Output

6

HINT

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

Solution

既然是“切”糕，所以我们考虑最小割。

从一个地方切断，代价为v，因此流量为v。

现在考虑D的限制条件。

容易发现，如果我们在(x,y)处向(x’,y’)(|x-x’|+|y-y’|)=1连流量为INF的边，那么最小割怎么也割不断这条边，因此，D的限制得以保证。

然后S连到所有底边的蛋糕，顶部蛋糕都连到T，跑一边最大流就是答案。

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int INF = 1<<30;
const int maxnode = 80005;
const int maxedge = maxnode * 10;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
typedef long long LL;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int D, c, k, g;
int V[42][42][42], id[42][42][42];
struct edge_type {
    int to, next, r;
} edge[maxedge];
int S, T, cnte = 1, h[maxnode];
int Q[maxnode];
void ins(int u, int v, int f) {
    ++cnte;
    edge[cnte].to = v;
    edge[cnte].r = f;
    edge[cnte].next = h[u];
    h[u] = cnte;
    ++cnte;
    edge[cnte].to = u;
    edge[cnte].r = 0;
    edge[cnte].next = h[v];
    h[v] = cnte;
}
int tail, head, d[maxnode], cur[maxnode];
bool bfs() {
    tail = head = 0;
    for (int i = S; i <= T; ++i) d[i] = -1;
    Q[tail++] = S;
    d[S] = 0;
    int now;
    while (head < tail) {
        now = Q[head++];
        for (int i = h[now]; i; i = edge[i].next) {
            if (d[edge[i].to] == -1 && edge[i].r) {
                d[edge[i].to] = d[now] + 1;
                Q[tail++] = edge[i].to;
            }
        }
    }
    return d[T] != -1;
}
int dfs(int now, int a) {
    if (T == now || a == 0) return a;
    int ret = 0, f;
    for (int &i = cur[now]; i; i = edge[i].next) {
        if (d[edge[i].to] != d[now]+1) continue;
        if (f = dfs(edge[i].to, min(a, edge[i].r))) {
            a -= f;
            ret += f;
            edge[i].r -= f;
            edge[i^1].r += f;
            if (a == 0) break;
        }
    }
    if (ret == 0) d[now] = -1;
    return ret;
}
int Dinic() {
    int ret = 0;
    while (bfs()) {
        for (int i = S; i <= T; ++i)
            cur[i] = h[i];
        ret += dfs(S, INF);
    }
    return ret;
}
int tot;
int main() {
	S = 1; tot = 2;
	c = getint(); k = getint(); g = getint();
	D = getint();
	for (int z = 0; z < g; ++z)
		for (int x = 1; x <= c; ++x)
			for (int y = 1; y <= k; ++y) {
				V[x][y][z] = getint();
				id[x][y][z] = tot++;
			}
	for (int x = 1; x <= c; ++x)
		for (int y = 1; y <= k; ++y)
			id[x][y][g] = tot++;
	T = tot;
	for (int z = 0; z < g; ++z)
		for (int x = 1; x <= c; ++x)
			for (int y = 1; y <= k; ++y)
				ins(id[x][y][z], id[x][y][z+1], V[x][y][z]);
	for (int z = D; z <= g; ++z)
		for (int x = 1; x <= c; ++x)
			for (int y = 1; y <= k; ++y) {
				int tx, ty;
				for (int i = 0; i < 4; ++i) {
					tx = x + dx[i]; ty = y + dy[i];
					if (1<=tx&&tx<=c&&1<=ty&&ty<=k)
						ins(id[x][y][z], id[tx][ty][z-D], INF);
				}
			}
	for (int x = 1; x <= c; ++x)
		for (int y = 1; y <= k; ++y) {
			ins(S, id[x][y][0], INF);
			ins(id[x][y][g], T, INF);
		}
	int ans = Dinic();
	printf("%d", ans);
}