[BZOJ3144/Luogu3227][HNOI2013]切糕(网络流)

发布于 2018-04-06  64 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3144/Luogu3227][HNOI2013]切糕(网络流)

Description

经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮她找出最好的切割方案。

出于简便考虑,我们将切糕视作一个长 P、宽 Q、高 R 的长方体点阵。我们将位于第 z层中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z),它有一个非负的不和谐值 v(x,y,z)。一个合法的切面满足以下两个条件:

与每个纵轴(一共有 P*Q 个纵轴)有且仅有一个交点。即切面是一个函数 f(x,y),对于所有 1≤x≤P, 1≤y≤Q,我们需指定一个切割点 f(x,y),且 1≤f(x,y)≤R。

切面需要满足一定的光滑性要求,即相邻纵轴上的切割点不能相距太远。对于所有的 1≤x,x’≤P 和 1≤y,y’≤Q,若|x-x’|+|y-y’|=1,则|f(x,y)-f(x’,y’)| ≤D,其中 D 是给定的一个非负整数。 可能有许多切面f 满足上面的条件,小A 希望找出总的切割点上的不和谐值最小的那个。

Tag

网络流

解决思路

转化为最小割,其实就是求一个权值最小的割面。
那么当没有对光滑性的限制的时候,就是求每一条竖线上的最小值,如果连成图论模型就是求每一条链上的最小割。
现在把光滑性的限制加入,即对于相邻的竖列,选择的割点的位置与当前列的差不能超过一个给定的值。
于是对于(u,v,w)的相邻的竖列,我们连边(u',v',w-k),流量为无限,这样就可以保证当我们选择了w高度时,相邻列中小于w-k的边都是不能被割掉的;两边一起限制,就可以使得题目的要求得以实现。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxMap=41;
const int maxN=maxMap*maxMap*maxMap;
const int maxM=maxN*5*2;
const int inf=2147483647;

class Edge
{
public:
    int v,flow;
};

int P,Q,R,S,T,D;
int Mat[maxMap][maxMap][maxMap],Id[maxMap][maxMap][maxMap];
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
int Depth[maxN],cur[maxN],Queue[maxN];

void Add_Edge(int u,int v,int flow);
bool Bfs();
int dfs(int u,int fa);

int main()
{
    ios::sync_with_stdio(false);mem(Head,-1);

    cin>>P>>Q>>R>>D;
    for (int k=1;k<=R;k++)
        for (int i=1;i<=P;i++)
            for (int j=1;j<=Q;j++)
                cin>>Mat[i][j][k];

    int idcnt=0;
    for (int i=1;i<=P;i++) for (int j=1;j<=Q;j++) for (int k=1;k<=R;k++) Id[i][j][k]=++idcnt;
    S=++idcnt;T=++idcnt;
    for (int i=1;i<=P;i++) for (int j=1;j<=Q;j++) Add_Edge(S,Id[i][j][1],Mat[i][j][1]);
    for (int k=1;k<R;k++)
        for (int i=1;i<=P;i++)
            for (int j=1;j<=Q;j++)//连限制边
            {
                Add_Edge(Id[i][j][k],Id[i][j][k+1],Mat[i][j][k+1]);
                if (k-D<0) continue;
                if (i!=1) Add_Edge(Id[i][j][k],Id[i-1][j][k-D],inf);
                if (i!=P) Add_Edge(Id[i][j][k],Id[i+1][j][k-D],inf);
                if (j!=1) Add_Edge(Id[i][j][k],Id[i][j-1][k-D],inf);
                if (j!=Q) Add_Edge(Id[i][j][k],Id[i][j+1][k-D],inf);
            }
    for (int i=1;i<=P;i++) for (int j=1;j<=Q;j++) Add_Edge(Id[i][j][R],T,Mat[i][j][R]);
    int Ans=0;
    while (Bfs())
    {
        for (int i=1;i<=T;i++) cur[i]=Head[i];
        while (int di=dfs(S,inf)) Ans+=di;
    }
    cout<<Ans<<endl;
    return 0;
}

void Add_Edge(int u,int v,int flow)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].v=u;E[edgecnt].flow=0;
    return;
}

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;Queue[1]=S;Depth[S]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((E[i].flow>0)&&(Depth[E[i].v]==-1))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
    }
    while (t!=h);
    if (Depth[T]==-1) return 0;
    return 1;
}

int dfs(int u,int flow)
{
    if (u==T) return flow;
    for (int &i=cur[u];i!=-1;i=Next[i])
        if ((E[i].flow>0)&&(Depth[E[i].v]==Depth[u]+1))
        {
            int di=dfs(E[i].v,min(flow,E[i].flow));
            if (di)
            {
                E[i].flow-=di;E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3144/Luogu3227][HNOI2013]切糕(网络流)


HNCJ OIer