BZOJ3144[Hnoi2013]切糕——最小割-白红宇

BZOJ3144[Hnoi2013]切糕——最小割

阅读量：6787 次

发布时间：2019-06-26

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

题目描述

输入

第一行是三个正整数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。

输出

仅包含一个整数，表示在合法基础上最小的总不和谐值。

样例输入

2 2 2

6 1

2 6

样例输出

提示

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

根据题意显然我们需要在二维平面的每个坐标上删除一个点。删除点不好办，我们将点转化成边：将第三维坐标为$z$的点变成连接第$z$层与第$z+1$层的边，即连接$(x,y,z)$与$(x,y,z+1)$，流量为$v(x,y,z)$，然后源点连向第一层的点，最后一层的点连向汇点。如果不考虑$D$的限制，直接按上述连边跑最小割即可。但现在考虑$D$的限制，我们将$(x,y,z)$连向$(x',y',z-D)$，流量为$INF$表示这条边不能被割。可以发现如果相邻两个坐标割的边第三维坐标差大于$D$时，就可以有流量绕过被割的边从相邻坐标的边流过去。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 1000000000using namespace std;int head[70000];int next[800000];int to[800000];int val[800000];int d[70000];int q[70000];int n,m,r,D;int f[50][50][50];int tot=1;int ans;int S,T;int dx[7]={0,1,0,-1};int dy[7]={1,0,-1,0};void add(int x,int y,int v){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; val[tot]=v; tot++; next[tot]=head[y]; head[y]=tot; to[tot]=x; val[tot]=0;}bool bfs(int S,int T){ int r=0; int l=0; memset(q,0,sizeof(q)); memset(d,-1,sizeof(d)); q[r++]=S; d[S]=0; while(l
                 
                  =1&&fx<=n&&fy>=1&&fy<=m) { add(calc(i,j,k),calc(fx,fy,k-D),INF); } } } add(calc(i,j,r+1),T,INF); } } dinic(); printf("%d",ans);}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10574345.html

你可能感兴趣的文章