最小割解决最优值最突出的特点就是要将对象划分到两个集合中
这题很明显，裸的最小割
先把点连成一根根柱子，就是p(x,y,k)-->p(x,y,k+1)流量是P(x,y,k+1)的不和谐值
然后s与p(x,y,1)连边，流量是p(x,y,1)的不和谐值
最后再将p(x,y,r)都连向t
下面就是解决切割限制了，其实很简单，就是我们通过连边是不满足限制的点不构成一个割的方案
具体来说就是，对于任意p(x,y,k) (k<r) 连p(x',y',k+d)--->p(x,y,k) 流量inf，x',y'为邻居
画图可知正确性
const inf=;
dx:array[..] of longint=(,,-,);
dy:array[..] of longint=(,-,,); type node=record
flow,next,point:longint;
end; var edge:array[..] of node;
pre,p,cur,numh,h,d:array[..] of longint;
num:array[..,..,..] of longint;
l,w,n,m,r,k,j,t,len,x,y,i:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; procedure build(x,y,f:longint);
begin
add(x,y,f);
add(y,x,);
end; function sap:longint;
var tmp,u,i,j,q,neck:longint;
begin
for i:= to t do
cur[i]:=p[i];
numh[]:=t+;
neck:=inf;
u:=;
sap:=;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
pre[j]:=u;
cur[u]:=i;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
q:=-;
tmp:=t;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then
if h[j]<tmp then
begin
q:=i;
tmp:=h[j];
end;
i:=edge[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
cur[u]:=q;
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m,r);
readln(l);
t:=;
for k:= to r do
for i:= to n do
for j:= to m do
begin
read(x);
inc(t);
num[k,i,j]:=t;
build(num[k-,i,j],t,x);
end;
inc(t);
for i:= to n do
for j:= to m do
begin
build(num[r,i,j],t,inf);
for w:= to do
begin
x:=i+dx[w];
y:=j+dy[w];
if (x>) and (x<=n) and (y>) and (y<=m) then
begin
for k:= to r-l do
build(num[k+l,x,y],num[k,i,j],inf);
end;
end;
end; writeln(sap);
end.