[HNOI2013]切糕

题目

先来考虑没有\(D\)的限制该怎么做

这不睿智题吗，每次对于矩阵上的每一个位置找一个最小的加起来

我们强行网络流一下

对于矩阵上的每一个位置\((i,j)\)，我们建出一条长度为\(h\)的链来，源点像链头连\(a_{1,i,j}\)的边，链尾像汇点连\(\infty\)的边，对于链中的第\(k\)个点，向\(k+1\)个点连一条\(a_{k+1,i,j}\)的边

这样我们跑一边最小割也就是答案了

考虑加入\(D\)的限制

不满足条件的情况是\(f(x,y)-f(i,j)>D\)，我们只需要连\((i,j,k)->(x,y,k-D)\)边权为\(\infty\)即可

这样我们保证了\((i,j)\)这个点选择割掉\(k+1\)或者更大的边的时候，\((x,y)\)不能割掉小于等于\(k-D\)的边

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int inf=999999999;
const int maxn=40*40*40+40;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
std::queue<int> q;
struct E{int v,nxt,f;}e[maxn<<2];
int head[maxn],cur[maxn],d[maxn];
int a[41][41][41],id[41][41][41],n,m,h,ans,D,S,T,num=1;
inline int BFS() {
    for(re int i=S;i<=T;i++) cur[i]=head[i],d[i]=0;
    d[S]=1,q.push(S);
    while(!q.empty()) {
        int k=q.front();q.pop();    
        for(re int i=head[k];i;i=e[i].nxt) 
        if(!d[e[i].v]&&e[i].f) d[e[i].v]=d[k]+1,q.push(e[i].v);
    }
    return d[T];
}
int dfs(int x,int now) {
    if(x==T||!now) return now;
    int flow=0,ff;
    for(re int& i=cur[x];i;i=e[i].nxt)
    if(d[e[i].v]==d[x]+1&&e[i].f) {
        ff=dfs(e[i].v,min(now,e[i].f));
        if(ff<=0) continue;
        flow+=ff,now-=ff,e[i].f-=ff,e[i^1].f+=ff;
        if(!now) break;
    }
    return flow;
}
inline void C(int x,int y,int f) {  
    e[++num].v=y;e[num].nxt=head[x];
    head[x]=num;e[num].f=f;
}
inline void add(int x,int y,int f) {C(x,y,f),C(y,x,0);}
int main() {
    n=read(),m=read(),h=read();D=read();
    for(re int k=1;k<=h;k++)
        for(re int i=1;i<=n;i++)
            for(re int j=1;j<=m;j++)
                a[k][i][j]=read(),id[k][i][j]=++T;
    ++T;
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) {
            add(S,id[1][i][j],a[1][i][j]);
            for(re int k=2;k<=h;k++)
                add(id[k-1][i][j],id[k][i][j],a[k][i][j]);
            add(id[h][i][j],T,inf); 
        }
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) 
            for(re int t=0;t<4;t++) {
                int x=i+dx[t],y=j+dy[t];
                if(x<1||y<1||x>n||y>m) continue;
                for(re int k=D+1;k<=h;k++)
                 add(id[k][i][j],id[k-D][x][y],inf);
            }
    while(BFS()) ans+=dfs(S,inf);
    printf("%d\n",ans);
    return 0;
}

[HNOI2013]切糕

原文：https://www.cnblogs.com/asuldb/p/10804707.html