[HNOI2013]切糕

时间：2023-03-09 02:44:08
[HNOI2013]切糕

题目描述

网址：https://daniu.luogu.org/problemnew/show/3227
大意：
平面上有一长方体，目标为将其切割为上下两半。
切割点为\((x,y,z)\)的点，每个点有一个不和谐值v，现在有两个要求：

  • [1]任何两个平面相邻的切割点之间的高度差不能超过D
  • [2]要使得最终的不和谐值最小。
    求解最小的$ ∑vi $

题目解法

直接建图，化点为边。将最下面的点与S相连，最上面的与T相连。
然后跑最小割即为答案。
现在关键在于如何限制高度差不超过D。
以\((x,y,z)\)与\((x+1,y,z)\)为例。
建立\((x,y,z) —>(x+1,y,z-D)\) 与 \((x+1,y,z+D+1)—>(x,y,z+1)\)两条边
那么在割断\((x,y,z)->(x,y,z+1)\)时，就可保证\((x+1,y)\)上割的为题目所限制范围。
动手画一下就明白了。 如果割超出范围的边，S、T依旧联通。
所以用上述方法建图，然后跑最小割即可得到答案。

实现代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define ll long long
#define RG register
#define IL inline
#define maxn 125000
#define INF 1e16+7
using namespace std;

IL ll gi(){
    RG ll date = 0, m = 1;  RG char ch = 0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch = getchar();
    if(ch == '-'){m = -1; ch = getchar();}
    while(ch>='0' && ch<='9')
       {date=date*10+ch-'0'; ch = getchar();}
    return date*m;
}

ll cnt,Q,P,R,S,T,D;
ll vis[maxn],dep[maxn],head[maxn],cur[maxn];
ll mx[4] = {0,0,-1,1},my[4] = {-1,1,0,0};
struct Road { ll to,next,cap,flow; }t[20*maxn];

IL bool Bfs(){
    for(RG ll i = 0; i <= T; i ++)vis[i] = 0;
    dep[S] = 0; vis[S] = 1; queue<ll>Que; Que.push(S);
    while(!Que.empty()){
        RG ll u = Que.front(); Que.pop();
        for(RG ll i = head[u]; i!= -1; i = t[i].next){
            RG ll v = t[i].to;
            if(!vis[v] && t[i].cap > t[i].flow){
                dep[v] = dep[u] + 1;
                vis[v] = true; Que.push(v);
            }
        }
    }return vis[T];
}

int Dfs(RG ll u,RG ll Lim){
    if(u == T || Lim == 0)return Lim;
    RG ll flow =0,f = 0;
    for(RG ll &i = cur[u]; i != -1; i = t[i].next){
        RG ll v = t[i].to;
        if(dep[v] == dep[u] + 1 && (f = Dfs(v,min(Lim,t[i].cap-t[i].flow))) > 0){
            flow += f; Lim -= f;
            t[i].flow += f; t[(i^1)].flow -= f;
            if(Lim == 0)break;
        }
    }return flow;
}

IL int Dinic(){
    RG ll Flow = 0;
    while(Bfs()){
        for(RG ll i = 0; i <= T; i ++)cur[i] = head[i];
        Flow += Dfs(S,INF);
    }return Flow;
}

IL ll Cod(RG ll z,RG ll x,RG ll y){
    return z*(P*Q) + (x-1)*Q + y;
}

IL void Add(ll uu,ll vv,ll cc){
    t[cnt++] = (Road){vv,head[uu],cc,0}; head[uu] = cnt - 1;
    t[cnt++] = (Road){uu,head[vv],0,0};  head[vv] = cnt - 1;
}

int main(){
    freopen("testdate.in","r",stdin);
    P = gi(); Q = gi(); R = gi(); D = gi();
    S = 0; T = R*P*Q+P*Q+1;
    for(RG ll i = 0; i <= T; i ++)head[i] = -1;
    for(RG ll h = 1; h <= R; h ++)
        for(RG ll i = 1; i <= P; i ++)
            for(RG ll j = 1; j <= Q; j ++)
                Add( Cod(h,i,j) , Cod(h-1,i,j) , gi());
    for(RG ll i = 1; i <= P; i ++)
        for(RG ll j = 1; j <= Q; j ++)
            Add(Cod(0,i,j),T,INF);
    for(RG ll i = 1; i <= P; i ++)
        for(RG ll j = 1; j <= Q; j ++)
            Add(S,Cod(R,i,j),INF);
    for(RG ll h = 1; h <= R; h ++)
        for(RG ll i = 1; i <= P; i ++)
            for(RG ll j = 1; j <= Q; j ++)
                for(RG ll f = 0; f < 4; f ++){
                    RG int x = mx[f]+i,y = my[f]+j;
                    if(x<1||y<1||x>P||y>Q)continue;
                    if(h-D>=0)Add(Cod(h-D,x,y),Cod(h,i,j),INF);
                    if(h+D<=R)Add(Cod(h,i,j),Cod(h+D,x,y),INF);
                }

    RG ll Ans = Dinic(); printf("%lld",Ans);
    return 0;
}

相关文章