ZigZagK

Never give up fighting!

[最小割]BZOJ3144(Hnoi2013)【切糕】题解

题目概述

有一块 \(X\times Y\times Z\) 的切糕,每个点 \((x,y,z)\) 都有不和谐值 \(v(x,y,z)\) 。现在要切这块切糕,为每个直线 \((x,y)\) 选出一个点 \(z\) ,一种切法的不和谐值为选出点的不和谐值之和,为了平整还需要满足两条相邻的直线选出的点距离不超过 \(D\) 。求最小不和谐值。

解题报告

声名远扬(?)的切糕模型,如果没有距离限制,我们可以把每个 \((x,y)\) 都从 \(S\)\(T\) 串起来,像这样:

S -> 1 -> 2 -> 3 -> ... -> T

将每条边的容量设置为不和谐值,然后求最小割就是最优解。

但是有限制,我们可以用容量为INF的边实现“屏蔽”效果,对于网络中的点 \((x,y,z)\) ,在 \((x,y,z-1-D)\to (x',y',z-1)\)\((x',y',z+D)\to (x,y,z)\) 之间( \((x,y)\)\((x',y')\) 相邻)连容量为INF的边,这样就会形成一个 \(S\to (x,y,z-1)\to (x',y',z-D)\to (x',y',z+D)\to (x,y,z)\to T\) 的“通路”,从而阻止其他边被选。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=40,maxt=maxn*maxn*maxn,maxe=(maxt+(maxt<<3))<<1;
const int fl[4][2]={{-1,0},{0,-1},{0,1},{1,0}},INF=2e9;

int X,Y,Z,D,n,ans;pair<int,int> e[maxe+5];
int E,lnk[maxt+5],son[maxe+5],nxt[maxe+5];
int que[maxt+5],dis[maxt+5],ti,vis[maxt+5],cur[maxt+5];

inline int ID(int x,int y,int z) {if (!z) return 0;return z<Z?(x-1)*Y*Z+(y-1)*Z+z:n+1;}
inline void Add(int x,int y,int z){
    son[E]=y;e[E]=mp(0,z);nxt[E]=lnk[x];lnk[x]=E++;
    son[E]=x;e[E]=mp(0,0);nxt[E]=lnk[y];lnk[y]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&e[j].fr<e[j].sc) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
        return vis[t]==ti;      
}
int Dfs(int x,int t,int MIN=INF){
    if (x==t||!MIN) return MIN;int f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],t,min(MIN,e[j].sc-e[j].fr)))){
            e[j].fr+=now;e[j^1].fr-=now;f+=now;
            if (!(MIN-=now)) break;
        }
    return f;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%d%d",&X,&Y,&Z,&D);n=X*Y*Z;E=0;memset(lnk,255,sizeof(lnk));
    for (int z=1;z<=Z;z++)
        for (int x=1;x<=X;x++)
            for (int y=1,val;y<=Y;y++)
                scanf("%d",&val),Add(ID(x,y,z-1),ID(x,y,z),val);
    for (int i=1;i<=X;i++)
        for (int j=1;j<=Y;j++)
            for (int f=0;f<4;f++){
                int x=i+fl[f][0],y=j+fl[f][1];
                if (x<1||x>X||y<1||y>Y) continue;
                for (int k=1;k<=Z;k++){
                    if (k>D+1) Add(ID(i,j,k-1),ID(x,y,k-1-D),INF);
                    if (k+D<Z) Add(ID(i,j,k+D),ID(x,y,k),INF);
                }
            }
    while (Bfs(0,n+1)) memcpy(cur,lnk,sizeof(lnk)),ans+=Dfs(0,n+1);
    return printf("%d\n",ans),0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注