「BZOJ3144」[HNOI2013] 切糕

2015年2月5日6,2881

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

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

题解

经典最小割模型

题面简化为,一个矩阵,每个格子分配一个数,不同的数字,代价不同,要求相邻格子数字差小等于d

求最小代价

每个格子拆出40个点

连同S与T用40种代价串起来

即 p(x,y,z)->p(x,y,z+1)边权f(x,y,z+1)

然后 p(x,y,z)->p(x’,y’,z-d)边权inf (x,y)与(x’,y’)相邻

把边画出来正确性很显然

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
eolv Recent comment authors
  Subscribe  
提醒
eolv
eolv

正确性很显然什么的黄学长简直太神了~