bzoj千题计划142：bzoj3144: [Hnoi2013]切糕

时间：2024-10-28 13:36:56

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

如果D=2 ，两个点，高度为4，建图如下

bzoj千题计划142：bzoj3144: [Hnoi2013]切糕

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 64005

#define M 323205

const int inf=2e9;

int n;

int P,Q,R,D;

int cost[][][];

int tot=;

int front[N],nxt[M<<],to[M<<],val[M<<],from[M<<];

int lev[N],num[N];

int path[N];

int cur[N];

int src,decc;

int dx[]={-,,,};

int dy[]={,,,-};

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c))  c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar();  }

}

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=w;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; val[tot]=;

   // cout<<u<<' '<<v<<' '<<w<<'\n';

}

bool bfs()

{

    queue<int>q;

    for(int i=src;i<=decc;++i) lev[i]=decc;

    q.push(decc);

    lev[decc]=;

    int now,t;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

        for(int i=front[now];i;i=nxt[i])

        {

            t=to[i];

            if(lev[t]==decc && val[i^])

            {

                lev[t]=lev[now]+;

                q.push(t);

            }

        }

    }

    return lev[src]!=decc;

}

int augment()

{

    int now=decc,flow=inf;

    int i;

    while(now!=src)

    {

        i=path[now];

        flow=min(flow,val[i]);

        now=from[i];

    }

    now=decc;

    while(now!=src)

    {

        i=path[now];

        val[i]-=flow;

        val[i^]+=flow;

        now=from[i];

    }

    return flow;

}

int isap()

{

    int flow=;

    if(!bfs()) return ;

    memset(num,,sizeof(num));

    for(int i=src;i<=decc;++i) num[lev[i]]++,cur[i]=front[i];

    int now=src,t;

    while(lev[src]<=decc)

    {

        if(now==decc)

        {

            flow+=augment();

            now=src;

        }

        bool advanced=false;

        for(int i=cur[now];i;i=nxt[i])

        {

            t=to[i];

            if(lev[t]==lev[now]- && val[i])

            {

                advanced=true;

                path[t]=i;

                cur[now]=i;

                now=t;

                break;

            }

        }

        if(!advanced)

        {

            int mi=decc;

            for(int i=front[now];i;i=nxt[i])

                if(val[i]) mi=min(mi,lev[to[i]]);

            if(!--num[lev[now]]) break;

            num[lev[now]=mi+]++;

            cur[now]=front[now];

            if(now!=src) now=from[path[now]];

        }

    }

       return flow;

}

int turn(int i,int j,int k)

{

    return ((i-)*Q+j-)*(R+)+k;

}

void build()

{

    int nx,ny;

    for(int i=;i<=P;++i)

        for(int j=;j<=Q;++j)

            for(int k=;k<=R;++k)

            {

                add(turn(i,j,k),turn(i,j,k+),cost[i][j][k]);

                if(k>D)

                {

                    for(int d=;d<;++d)

                    {

                        nx=i+dx[d]; ny=j+dy[d];

                        if(nx>= && nx<=P && ny>= && ny<=Q) add(turn(i,j,k),turn(nx,ny,k-D),inf);

                    }

                }

            }

    decc=P*Q*(R+)+;

    for(int i=;i<=P;++i)

        for(int j=;j<=Q;++j)

        {

            add(src,turn(i,j,),inf);

            add(turn(i,j,R+),decc,inf);

        }

}

int main()

{

    freopen("nutcake.in","r",stdin);

    freopen("nutcake.out","w",stdout);

    read(P); read(Q); read(R);

    read(D);

    for(int i=;i<=R;++i)

        for(int j=;j<=P;++j)

            for(int k=;k<=Q;++k)

            {

                read(cost[j][k][i]);

            //    cout<<j<<' '<<k<<' '<<i<<' '<<cost[j][k][i]<<'\n';

            }

    build();

    cout<<isap();

}

2018.3.20 考试代码

#include<queue>

#include<cstdio>

#include<iostream>

using namespace std;

const int inf=2e9;

#define M 400000

#define N 70000

int P,Q,R,D;

int a[][][];

int front[N],nxt[M<<],to[M<<],cap[M<<],tot=;

int src,decc;

int lev[N],cur[N];

queue<int>q;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void init()

{

    read(P); read(Q); read(R);

    read(D);

    for(int i=;i<=R;++i)

        for(int j=;j<=P;++j)

            for(int k=;k<=Q;++k)

                read(a[i][j][k]);

}

int turn(int i,int j,int k)

{

    return ((i-)*Q+j-)*(R+)+k;

}

void add(int u,int v,int val)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=val;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=;

}

void build()

{

    decc=(R+)*P*Q+;

    for(int i=;i<=P;++i)

        for(int j=;j<=Q;++j)

        {

            add(src,turn(i,j,),inf);

            for(int k=;k<=R;++k)

                add(turn(i,j,k),turn(i,j,k+),a[k][i][j]);

            add(turn(i,j,R+),decc,inf);

        }

    for(int i=;i<=P;++i)

        for(int j=;j<=Q;++j)

            for(int k=D+;k<=R+;++k)

            {

                if(i>) add(turn(i,j,k),turn(i-,j,k-D),inf);

                if(i<P) add(turn(i,j,k),turn(i+,j,k-D),inf);

                if(j>) add(turn(i,j,k),turn(i,j-,k-D),inf);

                if(j<Q) add(turn(i,j,k),turn(i,j+,k-D),inf);

            }

}

bool bfs()

{

    for(int i=src;i<=decc;++i) lev[i]=-,cur[i]=front[i];

    while(!q.empty()) q.pop();

    q.push(src);

    lev[src]=;

    int now;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

        for(int i=front[now];i;i=nxt[i])

            if(lev[to[i]]==- && cap[i])

            {

                lev[to[i]]=lev[now]+;

                if(to[i]==decc) return true;

                q.push(to[i]);

            }

    }

    return false;

}

int dinic(int now,int flow)

{

    if(now==decc) return flow;

    int delta,rest=;

    for(int &i=cur[now];i;i=nxt[i])

        if(lev[to[i]]==lev[now]+ && cap[i])

        {

            delta=dinic(to[i],min(flow-rest,cap[i]));

            if(delta)

            {

                rest+=delta;

                cap[i]-=delta; cap[i^]+=delta;

                if(rest==flow) break;

            }

        }

    if(rest!=flow) lev[now]=-;

    return rest;

}

void solve()

{

    int ans=;

    while(bfs()) ans+=dinic(src,inf);

    printf("%d",ans);

}

int main()

{

    freopen("cake.in","r",stdin);

    freopen("cake.out","w",stdout);

    init();

    build();

    solve();

}

3144: [Hnoi2013]切糕

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2143  Solved: 1165
[Submit][Status][Discuss]

Description

bzoj千题计划142：bzoj3144: [Hnoi2013]切糕

Input

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

Output

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

Sample Input

2 2 2
1
6 1
6 1
2 6
2 6

Sample Output

6

HINT

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

相关文章