AK-dream

题目描述

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

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

输入格式

输入文件第一行是三个正整数 $P$ , $Q$ , $R$ ,表示切糕的长 $P$ 、宽 $Q$ 、高 $R$ 。
第二行有一个非负整数 $D$ ,表示光滑性要求。
接下来是 $R$ 个 $P$ 行 $Q$ 列的矩阵,第 $z$ 个矩阵的第 $x$ 行第 $y$ 列是 $v(x,y,z) (1 \le x \le P, 1 \le y \le Q, 1 \le z \le R)$ 。

输出格式

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

题解

最小割 被CZH老师称作是模板题

首先看看第一个条件 对于每一个纵轴,我们都必须取一个高度$z$,表示这个纵轴从$z$这里切

我们可以这样来处理这件事情:

对于每条纵轴$(x,y)$,从源点连inf连向$(x,y,1)$,从$(x,y,R+1)$连inf连向汇点

然后对于每个$z\in [1,R]$,从$(x,y,z)$连一条流量为$v(x,y,z)$的边连向$(x,y,z+1)$,像一条链一样

由于最后求的是最小割,所以这$R$条边里总是要割掉一条的,符合我们的题意

这样第一个条件就处理完了 接下来是第二个条件

随脚画了一个图

这里我们假设D=2,那么对于每个点$(x,y,z)$,都要向 和它相邻的竖轴的 高度为$z-D$的那几个点各连一条inf

比如这个例子中,$(x,y,4)$要向$(x,y+1,2)$连一条边,$(x,y+1,4)$也要向$(x,y,2)$连边

这有什么用呢?假设我们割的是图中的这两条边,实际上就相当于在切糕上切了$(x,y,4)$和$(x,y+1,1)$这两个地方

这样增加了这种反向边之后,我们发现沿着蓝色路径依然可以从源点到汇点,也就是说割那两条边的方案不是一个合法割

它也确实和题意不符 因为$4-1=3>D$

这就解决了第二个限制条件

还有一个问题是我做题的时候想到的:万一最小割的方案在一条链上割了两条边怎么办?

实际上这种情况是不会出现的,画一画就能发现,如果一条链上割了两条边,那么重新连上其中一条边之后一定还是个合法割

代码

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
#include <bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

const int inf = 0x7fffffff;
int n, m, h, D, s, t;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int a[50][50][50], id[50][50][50], tot; // id[x][y][z]表示切糕上的(x,y,z)对应网络流里的哪个点
int now[100005], head[100005], pre[1000005], to[1000005], flow[1000005], sz = 1;

void addedge(int u, int v, int w) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v; flow[sz] = w;
}

int d[100005];

bool bfs() {
queue<int> q;
memset(d, 0, sizeof(d));
q.push(s); d[s] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (flow[i] && !d[y]) {
d[y] = d[x] + 1;
q.push(y);
}
}
}
return d[t];
}

int dfs(int x, int nowflow) {
if (!nowflow || x == t) return nowflow;
int rest = nowflow;
for (int i = now[x]; i; i = pre[i]) {
now[x] = i;
int y = to[i];
if (flow[i] && d[y] == d[x] + 1) {
int tmp = dfs(y, min(rest, flow[i]));
if (!tmp) d[y] = 0;
flow[i] -= tmp; flow[i^1] += tmp; rest -= tmp;
if (!rest) break;
}
}
return nowflow - rest;
}

int dinic() {
int ret = 0;
while (bfs()) {
for (int i = 0; i <= tot; i++) now[i] = head[i];
ret += dfs(s, inf);
}
return ret;
}

int main() {
read(n); read(m); read(h); read(D);
for (int k = 1; k <= h; k++) {
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
read(a[i][j][k]);
}
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
for (int k = 1; k <= h+1; k++) {
id[i][j][k] = ++tot;
}
}
s = 0, t = ++tot;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
addedge(s, id[i][j][1], inf); addedge(id[i][j][1], s, 0);
for (int k = 1; k <= h; k++) {
addedge(id[i][j][k], id[i][j][k+1], a[i][j][k]);
addedge(id[i][j][k+1], id[i][j][k], 0);
}
addedge(id[i][j][h+1], t, inf); addedge(t, id[i][j][h+1], 0);
for (int l = 0; l < 4; l++) {
int x = i + dir[l][0], y = j + dir[l][1];
if (1 <= x && x <= n && 1 <= y && y <= m) {
for (int k = 2; k + D <= h; k++) {
addedge(id[i][j][k+D], id[x][y][k], inf);
addedge(id[x][y][k], id[i][j][k+D], 0);
}
}
}
}
printf("%d\n", dinic());
return 0;
}

 评论