高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=3144

题意

一个n*m*k的立方体，从侧面切过去，切出一个N*M的切面（不是一个面，是崎岖的0.0），切到的每个点都有一个权值v（x,y,z）。

且切到的每个点与四周被切点的高度差（即z轴坐标的差）不能超过给定的D（切面要平滑0.0）。

最小化∑v(x,y,z){(x,y,z)∈切面}

题解

首先做k+1层n*m的点，对于第i层的每个点向i+1层的该点连容量为v（x,y,i)的边。

s向最下层的每个点连+∞的边，最上层连t，容量为+∞

这样之后就把点权转到了边上，做最小割。

然后处理高度差D的限制，

把第i层（x,y）的每个点向它处在i-D层的周围的点连+∞的边。

转换成割来考虑的话，就是如果把第i层（x,y）到i+1层的（x,y）割掉的话，

那么它周围的点必须割在差在D以内的边，画个图就很明显啦~~

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
const int N=100001,M=6000000;
const int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int u[M],v[M],w[M],next[M],head[N],k=1;
int d[N],pre[N],low[N],vd[N],cur[N];
int p,q,r,D,s,t;
 
int num(int x,int y,int z)
{   
    if(x<1||y<1||z<1||x>p||y>q||z>(r+1)) return N-1;
    return (z-1)*(p*q)+(x-1)*q+y;
}
 
int solve(int s,int t) 
{ 
    int now=s,i,ans=0; 
    low[s]=INT_MAX;vd[0]=t; 
    while(d[s]<t) 
    { 
        for(i=cur[now];i;i=next[i]) 
            if(w[i]>0 && d[now]==d[v[i]]+1) 
                break; 
        cur[now]=i; 
        if(i) 
        { 
            low[v[i]]=min(low[now],w[i]);pre[v[i]]=i;now=v[i]; 
            if(now==t) 
            { 
                for(;now!=s;now=u[pre[now]]) 
                    w[pre[now]]-=low[t],w[pre[now]^1]+=low[t]; 
                low[s]=INT_MAX;ans+=low[t]; 
            } 
        } 
        else
        { 
            if(!--vd[d[now]]) break; 
            d[now]=t; 
            for(i=head[now];i;i=next[i]) 
                if(w[i]>0 && d[now]>d[v[i]]+1) 
                    d[now]=d[v[i]]+1,cur[now]=i; 
            vd[d[now]]++; 
            if(now!=s)  now=u[pre[now]]; 
        } 
    } 
    return ans; 
}
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
int main()
{
    scanf("%d%d%d",&p,&q,&r);
    scanf("%d",&D);
    s=p*q*(r+2)+1;t=s+1;
    for(int i=1;i<=p;i++)
        for(int j=1;j<=q;j++)
        {
            add(num(i,j,r+1),t,INT_MAX);add(s,num(i,j,1),INT_MAX);
            for(int o=0;o<4;o++)
                add(num(i,j,r+1),num(i+dx[o],j+dy[o],r+1-D),INT_MAX);
        }
    int x;
    for(int k=1;k<=r;k++)
        for(int i=1;i<=p;i++)
            for(int j=1;j<=q;j++)
            {
                scanf("%d",&x);
                add(num(i,j,k),num(i,j,k+1),x);
                for(int o=0;o<4;o++)
                    add(num(i,j,k),num(i+dx[o],j+dy[o],k-D),INT_MAX);
            }
    printf("%d\n",solve(s,t));
}