BZOJ3144 Hnoi2013 切糕【网络流】*

BZOJ3144 Hnoi2013 切糕

Description

这里写图片描述

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的边
如图
这里写图片描述
然后就可以发现如果在另一个线段上割掉的不是[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;
}

BZOJ3144 Hnoi2013 切糕 【网络流】*