BZOJ3144：[HNOI2013]切糕—

BZOJ3144：[HNOI2013]切糕——题解

阅读量：5923 次

发布时间：2019-06-19

本文共 2375 字，大约阅读时间需要 7 分钟。

看着很像网络流，但是费用流貌似无法解决这个问题，其实甚至连忽略d的情况都做不到。

最小割？

将顶层和底层分成两个集合，切一次就相当于两个集合分开。

所以我们(i,j,k)->(i,j,k+1)边权为val(i,j,k)就可以做忽略d的情况了。

那么有d也很简单，只需要想你切完了一条边之后，不能让你身边的切哪些边即可。

画个图，我们就能发现(i,j,k)->(i,j,k-d)和(i,j,k+d+1)->(i,j,k+1)边权为INF就能保证如果切了非法的边仍然能保证连通。

（当然在遍历的时候后者的边也是前者的边，于是我们只需要加前者的边即可。）

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;const int B=42;const int N=B*B*B+B*B;const int M=N*20;const int INF=1e9;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int to,nxt,w;}e[M];int P,Q,R,D,cnt,head[N],cur[N],lev[N];int val[B][B][B],dui[N],r,S,T;int dx[4]={ 0,1,0,-1};int dy[4]={ 1,0,-1,0};inline void add(int u,int v,int w){ e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;}bool bfs(int m){ for(int i=1;i<=m;i++){ cur[i]=head[i];lev[i]=-1; } lev[S]=0;dui[r=0]=S; for(int l=0;l<=r;l++){ int u=dui[l]; for(int i=head[u];i!=-1;i=e[i].nxt){ int v=e[i].to; if(e[i].w&&lev[v]==-1){ dui[++r]=v; lev[v]=lev[u]+1; if(v==T)return 1; } } } return 0;}int dinic(int u,int flow,int m){ if(u==m)return flow; int res=0,delta; for(int &i=cur[u];i!=-1;i=e[i].nxt){ int v=e[i].to; if(lev[v]>lev[u]&&e[i].w){ delta=dinic(v,min(flow-res,e[i].w),m); if(delta){ res+=delta; e[i].w-=delta; e[i^1].w+=delta; if(res==flow)break; } } } if(res!=flow)lev[u]=-1; return res;}inline int num(int i,int j,int k){ return (k-1)*P*Q+(i-1)*Q+j;}int main(){ cnt=-1;memset(head,-1,sizeof(head)); P=read(),Q=read(),R=read(); D=read(); S=(R+1)*P*Q+1,T=S+1; for(int k=1;k<=R;k++) for(int i=1;i<=P;i++) for(int j=1;j<=Q;j++){ int u=num(i,j,k),v=num(i,j,k+1); add(u,v,read());add(v,u,0); if(k>D) for(int l=0;l<4;l++){ int nx=i+dx[l],ny=j+dy[l]; if(nx<1||nx>P||ny<1||ny>Q)continue; int nv=num(nx,ny,k-D); add(u,nv,INF);add(nv,u,0); } } for(int i=1;i<=P;i++) for(int j=1;j<=Q;j++){ int v=num(i,j,1),u=num(i,j,R+1); add(S,v,INF);add(v,S,0); add(u,T,INF);add(T,u,0); } int ans=0; while(bfs(T))ans+=dinic(S,INF,T); printf("%d\n",ans); return 0;}