[题解]bzoj3144(HNOI2013)切糕

本文主要是介绍[题解]bzoj3144(HNOI2013)切糕，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

        这道题是一个网络流的常见模型之一。不难想到源点向第1层连无限大的边，点(x,y,z)向点(x,y,z+1)连边权为v(x,y,z)的边。第r+1层向汇点连无限大的边。在相邻两竖列没有高度差限制的时候，这样的建图是正确的，即每竖列取最小。现在我们要构图来限制高度差。这是一个经典的构图模型：（下图是p=1，q=2，r=5，d=2的情况）

这里所有中间的边都是inf。图中省略了右上往左下连的边。为什么要加上中间的边呢？我们可以很明显的看出，我们在每一个竖列中至少要割掉一条边才能使图不联通。而图中可以看出，如果选了红色的边，那么所有蓝色的边相当于全部被割断。所以在一个竖列中至多只需要割一条边，因为如果割两条，下面那一条割断的效果就相当于割了上面那一条，所以没必要割上面那一条。在每竖列只割一条边的情况下，如果我们割了红色的边，那么我们必须割绿色边上方的边才能一次性割断S与T。而我们可以发现，每条连向斜下方的边都是连向相邻竖列比他低d格的点，这样正好就限制了高度。由于相邻两竖列互相连了边，所以就可以把相邻两竖列中割的边的高度差限制在d以内。然后只需要跑一边最大流就可以了。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int maxn=50,oo=0x7ffffff;
const int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
struct edge{int to,next,same,size;
}e[maxn<<16];
int p,q,r,d,num=0,top=0,v[maxn][maxn][maxn],head[maxn<<16],mark[maxn][maxn][maxn];
int que[maxn<<16],dep[maxn<<16],ans=0,cur[maxn<<16];void adde(int u,int v,int w){e[++num].to=v;e[num].size=w;e[num].next=head[u];head[u]=num;
}
void add(int u,int v,int w){adde(u,v,w);e[num].same=num+1;adde(v,u,0);e[num].same=num-1;
}
bool bfs(){memset(que,0,sizeof que);memset(dep,0,sizeof dep);int qhead=0,tail=1;dep[que[1]=0]=1;while(qhead<tail){int x=que[++qhead];for(int i=head[x];i;i=e[i].next){if(!dep[e[i].to]&&e[i].size){dep[e[i].to]=dep[x]+1;que[++tail]=e[i].to;if(e[i].to==top+1)return true;}}}return false;
}
int dfs(int x,int flow){if(x==top+1||(!flow))return flow;int temp=0;for(int &i=cur[x];i;i=e[i].next){if(dep[e[i].to]==dep[x]+1&&(temp=dfs(e[i].to,min(flow,e[i].size)))){e[i].size-=temp;e[e[i].same].size+=temp;return temp;}}return 0;
}
int Dinic(){int flow;while(bfs()){memcpy(cur,head,sizeof head);while(flow=dfs(0,oo))ans+=flow;}
}int main(){scanf("%d%d%d%d",&p,&q,&r,&d);for(int i=1;i<=r+1;i++){for(int j=1;j<=p;j++){for(int k=1;k<=q;k++){mark[j][k][i]=++top;}}}for(int i=1;i<=p;i++){for(int j=1;j<=q;j++){add(0,mark[i][j][1],oo);add(mark[i][j][r+1],top+1,oo);}}for(int i=1;i<=r;i++){for(int j=1;j<=p;j++){for(int k=1;k<=q;k++){scanf("%d",&v[j][k][i]);add(mark[j][k][i],mark[j][k][i+1],v[j][k][i]);}}}for(int i=d+1;i<=r+1;i++){for(int j=1;j<=p;j++){for(int k=1;k<=q;k++){for(int mv=1;mv<=4;mv++){if(mark[j+dx[mv]][k+dy[mv]][i]){add(mark[j][k][i],mark[j+dx[mv]][k+dy[mv]][i-d],oo);}}}}}Dinic();printf("%d\n",ans);
}

这篇关于[题解]bzoj3144(HNOI2013)切糕的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---