BruceJay's Blog

BZOJ3144 切糕

| Comments

To start with

网络流%%%%%

Problem

Solution

非常经典的最小割模型。
简化下题意:一个P行Q列的棋盘,每个格子选个[1,R]间的数f(x,y),选每个数有个代价cost(x,y,z),要求代价最小且相邻格子选数的绝对值只差不大于D。
将每个格子拆成R个。(x,y,z-1)向(x,y,z)连一条容量为cost(x,y,z)的边,割掉这条边表示格子(x,y)选了数z。
因为有D的限制,所以(x,y,z)向(x',y',z-d)连一条容量无限的边,(x,y)与(x',y')相邻。如果f(x,y)-d>f(x',y'),会存在一条S到T的路径(画个图就知道了)。

Code

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

const int N = 45;
const int Size = 64100;
const int M = 1000100;
const int INF = 0x3f3f3f3f;
struct Edge{int u,v,cap,flow,nxt;}e[M];
int head[Size]; int cur[Size]; int h[Size];
int a[N][N][N]; int p[N][N][N];
queue<int> q;
int P,Q,R,D,T,cnt=0,ans=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v,int cap)
{
    e[++cnt]=(Edge){u,v,cap,0,head[u]}; head[u]=cnt;
    e[++cnt]=(Edge){v,u,0,0,head[v]}; head[v]=cnt;
}

void Build()
{
    cnt=1;
    for(int x=1;x<=P;x++)
    for(int y=1;y<=Q;y++){
        for(int z=1;z<=R;z++){
            Addedge(p[x][y][z-1],p[x][y][z],a[x][y][z]);
            if(z>D){
                if(x) Addedge(p[x][y][z],p[x-1][y][z-D],INF);
                if(y) Addedge(p[x][y][z],p[x][y-1][z-D],INF);
                if(x<P) Addedge(p[x][y][z],p[x+1][y][z-D],INF);
                if(y<Q) Addedge(p[x][y][z],p[x][y+1][z-D],INF);
            }
        }
        Addedge(p[x][y][R],T,INF);
    }
}

bool Bfs()
{
    memset(h,-1,sizeof(h));
    h[0]=0; q.push(0);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].nxt)
            if(h[e[i].v]==-1 && e[i].cap>e[i].flow){
                h[e[i].v]=h[u]+1; q.push(e[i].v);
            }
    }
    return h[T]!=-1;
}

int Dfs(int u,int now)
{
    int flow=0;
    if(u==T || !now) return now;
    for(int& i=cur[u];i;i=e[i].nxt)
        if(h[e[i].v]==h[u]+1){
            int f=Dfs(e[i].v,min(now,e[i].cap-e[i].flow));
            e[i].flow+=f; e[i^1].flow-=f;
            flow+=f; now-=f; if(!now) break;
        }
    return flow;
}

void Dinic()
{
    while(Bfs()){
        memcpy(cur,head,sizeof(cur));
        ans+=Dfs(0,INF);
    }
}

int main()
{
    freopen("3144.in","r",stdin);
    freopen("3144.out","w",stdout);
    P=read(); Q=read(); R=read();
    T=P*Q*R+1; D=read();
    for(int z=1;z<=R;z++)
    for(int x=1;x<=P;x++)
    for(int y=1;y<=Q;y++){
        a[x][y][z]=read();
        p[x][y][z]=++cnt;
    }
    Build();
    Dinic();
    printf("%d",ans);
    return 0;
}

Last but not least

感觉这题建图方式蛮难想的。

Comments

comments powered by Disqus