bzoj 3144 切糕 —— 最小割

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3144

每个点拆成 R 个，连成一条链，边上是权值，割掉代表选这一层；

然后每个点的第 t 层向四周的点的第 t-d 层连边，就能达到选了第 i 条边，则四周的点必须选 i-d ~ T 范围的边，而对方反过来一连，就限制在 i-d ~ i+d 了；

竟然因为忘记 ct=1 而调了一小时呵呵...

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const xn=,xm=xn*,inf=1e9;

int n,m,H,hd[xn],ct=,to[xm],nxt[xm],c[xm],dis[xn],cur[xn],S,T;

queue<int>q;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void ade(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;}

void add(int x,int y,int z){ade(x,y,z); ade(y,x,);}

int id(int x,int y,int k){return ((x-)*m+y-)*H+k;}

bool bfs()

{

  for(int i=S;i<=T;i++)dis[i]=;

  dis[S]=; q.push(S);

  while(q.size())

    {

      int x=q.front(); q.pop();

      for(int i=hd[x],u;i;i=nxt[i])

    if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);

    }

  return dis[T];

}

int dfs(int x,int fl)

{

  if(x==T)return fl;

  int ret=;

  for(int &i=cur[x],u;i;i=nxt[i])

    {

      if(dis[u=to[i]]!=dis[x]+||!c[i])continue;

      int tmp=dfs(u,min(fl-ret,c[i]));

      if(!tmp)dis[u]=;

      c[i]-=tmp; c[i^]+=tmp;

      ret+=tmp; if(ret==fl)break;

    }

  return ret;

}

int main()

{

  n=rd(); m=rd(); H=rd(); int d=rd(); S=; T=n*m*H+;

  for(int t=;t<=H;t++)

    for(int i=;i<=n;i++)

      for(int j=,x;j<=m;j++)

    {

      x=rd(); int nw=id(i,j,t);

      if(t==)add(S,nw,x); else add(id(i,j,t-),nw,x);

      if(t==H)add(nw,T,inf);

      if(t<=d)continue; int k=t-d;//

      if(i>)add(nw,id(i-,j,k),inf);

      if(j>)add(nw,id(i,j-,k),inf);

      if(i<n)add(nw,id(i+,j,k),inf);

      if(j<m)add(nw,id(i,j+,k),inf);

    }

  int ans=;

  while(bfs())

    {

      memcpy(cur,hd,sizeof hd);

      ans+=dfs(S,inf);

    }

  printf("%d\n",ans);

  return ;

}