BZOJ3144 Hnoi2013 切糕

Description

BZOJ3144 Hnoi2013 切糕【网络流】*-LMLPHP

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

HINT

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

震惊，加边写错了导致调了40分钟

然后这题是一个比较经典的网络流建模

我们可以把相邻的两个纵向的R轴抽象成两条线，然后我们需要在这两条线上各割掉一条边且这两条边的位置不能差D

然后考虑建模

对于一个点Z，连一条到Z-D流量INF的边

如图

BZOJ3144 Hnoi2013 切糕【网络流】*-LMLPHP

然后就可以发现如果在另一个线段上割掉的不是[Z-D,Z+D]区间的是不会成功地割掉一条边的

所以就这样建模

注意题目中RPQ的顺序，贼坑

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 70000

int P,Q,R,D;

int val[45][45][45];

int mx[4]={0,0,1,-1};

int my[4]={1,-1,0,0};

namespace Dinic{

    struct Edge{

        int u,v,cap,flow;

        Edge(int u,int v,int cap,int flow):u(u),v(v),cap(cap),flow(flow){}

    };

    int s,t;

    int vis[N],d[N];

    vector<Edge> E;

    vector<int> g[N];

    void add(int u,int v,int cap){

        E.push_back(Edge(u,v,cap,0));

        E.push_back(Edge(v,u,0,0));

        int m=E.size();

        g[u].push_back(m-2);

        g[v].push_back(m-1);

    }

    bool bfs(){

        static queue<int> q;

        memset(vis,0,sizeof(vis));

        memset(d,0,sizeof(d));

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

        q.push(s);

        d[s]=1;vis[s]=1;

        while(!q.empty()){

            int u=q.front();q.pop();

            for(int i=0;i<(int)g[u].size();i++){

                Edge e=E[g[u][i]];

                if(e.cap>e.flow&&(!vis[e.v])){

                    vis[e.v]=1;

                    d[e.v]=d[u]+1;

                    q.push(e.v);

                }

            }

        }

        return vis[t];

    }

    int dfs(int u,int a){

        if(u==t||(!a))return a;

        int flow=0;

        for(int i=0;i<(int)g[u].size();i++){

            Edge &e=E[g[u][i]];

            if(d[e.v]!=d[u]+1)continue;

            int f=dfs(e.v,min(a,e.cap-e.flow));

            if(!f)continue;

            e.flow+=f;

            E[g[u][i]^1].flow-=f;

            a-=f;

            flow+=f;

            if(!a)return flow;

        }

        if(!flow)d[u]=0;

        return flow;

    }

    int Max_flow(){

        int flow=0;

        while(bfs())flow+=dfs(s,INF);

        return flow;

    }

    int getid(int z,int x,int y){return (x-1)*Q+y+z*P*Q;}

    void build(){

        s=0;t=(R+1)*P*Q+1;

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

            for(int k=1;k<=Q;k++)add(s,getid(0,j,k),INF),add(getid(R,j,k),t,INF);

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

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

                for(int k=1;k<=Q;k++)add(getid(i-1,j,k),getid(i,j,k),val[i][j][k]);

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

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

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

                    for(int l=0;l<=4;l++){

                        int nx=j+mx[l],ny=k+my[l];

                        if(nx<1||nx>P||ny<1||ny>Q)continue;

                        add(getid(i,j,k),getid(i-D,nx,ny),INF);

                    }

    }

    void solve(){

        scanf("%d%d%d",&P,&Q,&R);

        scanf("%d",&D);

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

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

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

                    scanf("%d",&val[i][j][k]);

        build();

        printf("%d",Max_flow());

    }

};

int main(){

    using namespace Dinic;

    solve();

    return 0;

}

切糕