http://www.elijahqi.win/2017/12/04/bzoj3144luogu3227hnoi2013%e5%88%87%e7%b3%95/
題目描述
經過千辛萬苦小 A 得到了一塊切糕，切糕的形狀是長方體，小 A 打算攔腰将切糕切成兩半分給小 B。出于美觀考慮，小 A 希望切面能盡量光滑且和諧。于是她找到你，希望你能幫她找出最好的切割方案。
出于簡便考慮，我們将切糕視作一個長 P、寬 Q、高 R 的長方體點陣。我們将位于第 z層中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的點稱為(x,y,z)，它有一個非負的不和諧值 v(x,y,z)。一個合法的切面滿足以下兩個條件：
與每個縱軸(一共有 P*Q 個縱軸)有且僅有一個交點。即切面是一個函數 f(x,y)，對于所有 1≤x≤P, 1≤y≤Q,我們需指定一個切割點 f(x,y),且 1≤f(x,y)≤R。
切面需要滿足一定的光滑性要求，即相鄰縱軸上的切割點不能相距太遠。對于所有的 1≤x,x’≤P 和 1≤y,y’≤Q，若|x-x’|+|y-y’|=1，則|f(x,y)-f(x’,y’)| ≤D，其中 D 是給定的一個非負整數。 可能有許多切面f 滿足上面的條件，小A 希望找出總的切割點上的不和諧值最小的那個。 輸入輸出格式
輸入格式：
第一行是三個正整數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。
輸出格式：
僅包含一個整數，表示在合法基礎上最小的總不和諧值。
輸入輸出樣例
輸入樣例#1： 複制
2 2 2
1
6 1
6 1
2 6
2 6
輸出樣例#1： 複制
6
說明
最佳切面的f為f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1
從别的blog盜了一張圖來
然後整個過程就顯得非常清楚了 我們思考假設我們沒有高度限制 那我是不是就是跑一下最小割即可 為什麼最小割 因為我需要總的費用 總的不優美程度最小
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define N 125000
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
return x*f;
}
int dx[]={0,1,-1,0},dy[]={1,0,0,-1};
int p,q,r,T,num=1,h[N],level[N],mp[44][44][44],nn,d;
struct node{
int x,y,z,next;
}data[N<<3];
inline int calc(int x,int y,int z){if (z==0) return 0;return (z-1)*nn+(x-1)*q+y;}
inline void insert1(int x,int y,int z){
data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;data[num].x=x;
data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;data[num].x=y;
}
inline bool bfs(){
memset(level,0,sizeof(level));level[0]=1;queue<int>q;q.push(0);
while(!q.empty()){
int x=q.front();q.pop();
for (int i=h[x];i;i=data[i].next){
int y=data[i].y,z=data[i].z;if (level[y]||!z) continue;
level[y]=level[x]+1;q.push(y);if (y==T) return 1;
}
}return 0;
}
inline int dfs(int x,int s){
if (x==T) return s;int ss=s;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y,z=data[i].z;
if (level[x]+1==level[y]&&z){
int xx=dfs(y,min(z,s));if (!xx) level[y]=0;
s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss;
}
}return ss-s;
}
int main(){
freopen("bzoj3144.in","r",stdin);
p=read();q=read();r=read();nn=p*q;T=calc(p,q,r)+1;int ans=0;d=read();
for (int i=1;i<=r;++i)
for (int j=1;j<=p;++j)
for (int z=1;z<=q;++z) mp[j][z][i]=read();
for (int i=1;i<=p;++i)
for (int j=1;j<=q;++j){
for (int z=1;z<=r;++z){
insert1(calc(i,j,z-1),calc(i,j,z),mp[i][j][z]);
if (z>d)
for (int k=0;k<4;++k){
int x1=i+dx[k],y1=j+dy[k];if (x1<1||y1<1||x1>p||y1>q) continue;
insert1(calc(i,j,z),calc(x1,y1,z-d),inf);
}
}insert1(calc(i,j,r),T,inf);
}
while(bfs()) ans+=dfs(0,inf);
printf("%d",ans);
return 0;
}