3144: [Hnoi2013]切糕
http://www.lydsy.com/JudgeOnline/problem.php?id=3144
RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
405097 | Liu_Ts | 3144 | Accepted | 96900 kb | 1516 ms | C++ | 1941 B | 2013-05-05 09:58:21 |
题意
一个n*m*k的立方体,从侧面切过去,切出一个N*M的切面(不是一个面,是崎岖的0.0),切到的每个点都有一个权值v(x,y,z)。
且切到的每个点与四周被切点的高度差(即z轴坐标的差)不能超过给定的D(切面要平滑0.0)。
最小化∑v(x,y,z){(x,y,z)∈切面}
题解
首先做k+1层n*m的点,对于第i层的每个点向i+1层的该点连容量为v(x,y,i)的边。
s向最下层的每个点连+∞的边,最上层连t,容量为+∞
这样之后就把点权转到了边上,做最小割。
然后处理高度差D的限制,
把第i层(x,y)的每个点向它处在i-D层的周围的点连+∞的边。
转换成割来考虑的话,就是如果把第i层(x,y)到i+1层的(x,y)割掉的话,
那么它周围的点必须割在差在D以内的边,画个图就很明显啦~~
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<climits> using namespace std; const int N=100001,M=6000000; const int dx[]={0,0,-1,1},dy[]={1,-1,0,0}; int u[M],v[M],w[M],next[M],head[N],k=1; int d[N],pre[N],low[N],vd[N],cur[N]; int p,q,r,D,s,t; int num(int x,int y,int z) { if(x<1||y<1||z<1||x>p||y>q||z>(r+1)) return N-1; return (z-1)*(p*q)+(x-1)*q+y; } int solve(int s,int t) { int now=s,i,ans=0; low[s]=INT_MAX;vd[0]=t; while(d[s]<t) { for(i=cur[now];i;i=next[i]) if(w[i]>0 && d[now]==d[v[i]]+1) break; cur[now]=i; if(i) { low[v[i]]=min(low[now],w[i]);pre[v[i]]=i;now=v[i]; if(now==t) { for(;now!=s;now=u[pre[now]]) w[pre[now]]-=low[t],w[pre[now]^1]+=low[t]; low[s]=INT_MAX;ans+=low[t]; } } else { if(!--vd[d[now]]) break; d[now]=t; for(i=head[now];i;i=next[i]) if(w[i]>0 && d[now]>d[v[i]]+1) d[now]=d[v[i]]+1,cur[now]=i; vd[d[now]]++; if(now!=s) now=u[pre[now]]; } } return ans; } void add(int x,int y,int z) { u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k; u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k; } int main() { scanf("%d%d%d",&p,&q,&r); scanf("%d",&D); s=p*q*(r+2)+1;t=s+1; for(int i=1;i<=p;i++) for(int j=1;j<=q;j++) { add(num(i,j,r+1),t,INT_MAX);add(s,num(i,j,1),INT_MAX); for(int o=0;o<4;o++) add(num(i,j,r+1),num(i+dx[o],j+dy[o],r+1-D),INT_MAX); } int x; for(int k=1;k<=r;k++) for(int i=1;i<=p;i++) for(int j=1;j<=q;j++) { scanf("%d",&x); add(num(i,j,k),num(i,j,k+1),x); for(int o=0;o<4;o++) add(num(i,j,k),num(i+dx[o],j+dy[o],k-D),INT_MAX); } printf("%d\n",solve(s,t)); }