首页 > 题解 > bzoj 3144 [Hnoi2013]切糕

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

题解

首先不考虑d的限制,那么就可以对于每一竖列连一链点,割掉最小的,就是答案。

那么d的限制该怎么办呢?

我们可以用一些inf的边来”屏蔽”那些不能割的边

其实只要从z向”相邻的”路径的z-d号点连inf的边即可

这样要是隔了距离大于d的边,还是可以通过inf的边流到T的(画个图就能理解了)


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×