P3227 [HNOI2013] 切糕

题意:
$n\ast m$的矩阵,每个点可以选择一个值$a_{i,j}=k$,然后你能获得$w(i,j,k)$的得分，但是相邻两点之间的差值有限制，让你求最大得分。

考虑最小割。

每个点$(i,j)$弄出一条长为$R+1$的链，其中$k->k+1$的流量为$w(i,j,k)$。

考虑限制，只需要从这条链的$k$到相邻一条链的$k-d$连一无穷大的边，因为如果相邻的链选择的点$<k-d$那么就会有流量剩余，因此就能进行限制了。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=5e5+10;
int n,m,k,d;
int h[N],st,ed,cur[N];
int tot=1,hd[N],ver[N*5],nxt[N*5],w[N*5];
int a[50][50][50],id[50][50][50],cnt;
void add(int x,int y,int z){tot++;ver[tot]=y;w[tot]=z;nxt[tot]=hd[x];hd[x]=tot;
}
void link(int x,int y,int z){add(x,y,z),add(y,x,0);
}
bool bt_h(){memset(h,0,sizeof(h));h[st]=1;queue<int>q;q.push(st);while(q.size()){int x=q.front();q.pop();for(int i=hd[x];i;i=nxt[i]){int y=ver[i];if(w[i]&&!h[y]){h[y]=h[x]+1;q.push(y);}}}return h[ed];
}
int findflow(int x,int f){if(x==ed)return f;int res=f,tt;for(int &i=cur[x];i;i=nxt[i]){int y=ver[i];if(w[i]&&h[y]==h[x]+1){tt=findflow(y,min(res,w[i]));w[i]-=tt,w[i^1]+=tt;res-=tt;if(!res)break;}}if(res==f)h[x]=0;return f-res;
}
int dicnic(){int ans=0;while(bt_h()){memcpy(cur,hd,sizeof(cur));ans+=findflow(st,1e9);}return ans;
}
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
void solve(){qr(n),qr(m),qr(k),qr(d);rep(ki,1,k){rep(i,1,n)rep(j,1,m)qr(a[ki][i][j]);}rep(ki,1,k+1){rep(i,1,n)rep(j,1,m)id[ki][i][j]=++cnt;}st=cnt+1,ed=st+1;rep(i,1,n)rep(j,1,m){link(st,id[1][i][j],1e7);link(id[k+1][i][j],ed,1e7);}rep(ki,1,k){rep(i,1,n)rep(j,1,m){link(id[ki][i][j],id[ki+1][i][j],a[ki][i][j]);}if(ki>d){rep(i,1,n)rep(j,1,m){rep(t,0,3){int x=i+dx[t],y=j+dy[t];if(1<=x&&x<=n&&1<=y&&y<=m){link(id[ki][i][j],id[ki-d][x][y],1e7);}}}}}qw(dicnic());puts("");
}
int main(){int tt;tt=1;while(tt--)solve();return 0;
}