题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3144
一根纵轴上切一个点，可以把一根纵轴上的点连成一串来体现。自己的写法是每个点连向前一个点的边上放着权值。
相邻位置高度的限制可以在两条链之间连边来体现；自己的高度是 i 的话，自己向旁边的 i-D-1 连边，这样切了自己就必须切旁边 i-D 及其后的点；旁边的 i+D 向自己连边，这样切了自己就必须切旁边 i+D 及其前的点。这样就能限制住了。
似乎可以只连一条，另一条在做到对方的时候自然会和自己连上；但自己的写法里 i-D-1 和 i+D 不是对称的，所以做到对方的时候不能恰好把自己的那条边连上。可能因为这样连的边多了，自己跑得还挺慢的。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=64005,M=384085,INF=7e7; int n,m,h,D,t,bh[45][45][45]; int hd[N],xnt=1,cur[N],to[M],nxt[M],cap[M]; int dfn[N],q[N],he,tl; int Mn(int a,int b){return a<b?a:b;} int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } void add(int x,int y,int z) { to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=z; to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=0; } bool bfs() { memset(dfn,0,sizeof dfn);dfn[0]=1; q[he=tl=1]=0; while(he<=tl) { int k=q[he++]; for(int i=hd[k],v;i;i=nxt[i]) if(cap[i]&&!dfn[v=to[i]]) dfn[v]=dfn[k]+1,q[++tl]=v; } return dfn[t]; } int deb; int dinic(int cr,int flow) { if(cr==t)return flow; int use=0; for(int& i=cur[cr],v;i;i=nxt[i]) if(cap[i]&&dfn[v=to[i]]==dfn[cr]+1) { int tmp=dinic(v,Mn(flow-use,cap[i])); if(!tmp)dfn[v]=0; use+=tmp;cap[i]-=tmp;cap[i^1]+=tmp; if(use==flow)return use; } return use; } int main() { n=rdn();m=rdn();h=rdn();D=rdn(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=h;k++) bh[i][j][k]=++t; t++; for(int k=1;k<=h;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int d=rdn(),cr=bh[i][j][k]; add(bh[i][j][k-1],cr,d); int x=k-D-1,y=k+D;//D not d!!! if(x>0) { if(i>1)add(cr,bh[i-1][j][x],INF); if(j>1)add(cr,bh[i][j-1][x],INF); if(i<n)add(cr,bh[i+1][j][x],INF); if(j<m)add(cr,bh[i][j+1][x],INF); } if(y<h) { if(i>1)add(bh[i-1][j][y],cr,INF); if(j>1)add(bh[i][j-1][y],cr,INF); if(i<n)add(bh[i+1][j][y],cr,INF); if(j<m)add(bh[i][j+1][y],cr,INF); } } for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)add(bh[i][j][h],t,INF); int ans=0; while(bfs())memcpy(cur,hd,sizeof hd),ans+=dinic(0,INF); printf("%d ",ans); return 0; }