BZOJ 3144: [Hnoi2013]切糕

Description

《BZOJ 3144: [Hnoi2013]切糕》

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

#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);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据