http://www.lydsy.com/JudgeOnline/problem.php?id=3144
如果D=2 ，两个点，高度为4，建图如下
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 64005
#define M 323205
const int inf=2e9; int n; int P,Q,R,D;
int cost[][][]; int tot=;
int front[N],nxt[M<<],to[M<<],val[M<<],from[M<<];
int lev[N],num[N];
int path[N];
int cur[N]; int src,decc; int dx[]={-,,,};
int dy[]={,,,-}; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; val[tot]=;
// cout<<u<<' '<<v<<' '<<w<<'\n';
} bool bfs()
{
queue<int>q;
for(int i=src;i<=decc;++i) lev[i]=decc;
q.push(decc);
lev[decc]=;
int now,t;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==decc && val[i^])
{
lev[t]=lev[now]+;
q.push(t);
}
}
}
return lev[src]!=decc;
} int augment()
{
int now=decc,flow=inf;
int i;
while(now!=src)
{
i=path[now];
flow=min(flow,val[i]);
now=from[i];
}
now=decc;
while(now!=src)
{
i=path[now];
val[i]-=flow;
val[i^]+=flow;
now=from[i];
}
return flow;
} int isap()
{
int flow=;
if(!bfs()) return ;
memset(num,,sizeof(num));
for(int i=src;i<=decc;++i) num[lev[i]]++,cur[i]=front[i];
int now=src,t;
while(lev[src]<=decc)
{
if(now==decc)
{
flow+=augment();
now=src;
}
bool advanced=false;
for(int i=cur[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==lev[now]- && val[i])
{
advanced=true;
path[t]=i;
cur[now]=i;
now=t;
break;
}
}
if(!advanced)
{
int mi=decc;
for(int i=front[now];i;i=nxt[i])
if(val[i]) mi=min(mi,lev[to[i]]);
if(!--num[lev[now]]) break;
num[lev[now]=mi+]++;
cur[now]=front[now];
if(now!=src) now=from[path[now]];
}
}
return flow;
} int turn(int i,int j,int k)
{
return ((i-)*Q+j-)*(R+)+k;
} void build()
{
int nx,ny;
for(int i=;i<=P;++i)
for(int j=;j<=Q;++j)
for(int k=;k<=R;++k)
{
add(turn(i,j,k),turn(i,j,k+),cost[i][j][k]);
if(k>D)
{
for(int d=;d<;++d)
{
nx=i+dx[d]; ny=j+dy[d];
if(nx>= && nx<=P && ny>= && ny<=Q) add(turn(i,j,k),turn(nx,ny,k-D),inf);
}
}
}
decc=P*Q*(R+)+;
for(int i=;i<=P;++i)
for(int j=;j<=Q;++j)
{
add(src,turn(i,j,),inf);
add(turn(i,j,R+),decc,inf);
}
} int main()
{
freopen("nutcake.in","r",stdin);
freopen("nutcake.out","w",stdout);
read(P); read(Q); read(R);
read(D);
for(int i=;i<=R;++i)
for(int j=;j<=P;++j)
for(int k=;k<=Q;++k)
{
read(cost[j][k][i]);
// cout<<j<<' '<<k<<' '<<i<<' '<<cost[j][k][i]<<'\n';
}
build();
cout<<isap();
}
2018.3.20 考试代码
#include<queue>
#include<cstdio>
#include<iostream> using namespace std; const int inf=2e9; #define M 400000
#define N 70000 int P,Q,R,D;
int a[][][]; int front[N],nxt[M<<],to[M<<],cap[M<<],tot=; int src,decc;
int lev[N],cur[N];
queue<int>q; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void init()
{
read(P); read(Q); read(R);
read(D);
for(int i=;i<=R;++i)
for(int j=;j<=P;++j)
for(int k=;k<=Q;++k)
read(a[i][j][k]);
} int turn(int i,int j,int k)
{
return ((i-)*Q+j-)*(R+)+k;
} void add(int u,int v,int val)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=val;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=;
} void build()
{
decc=(R+)*P*Q+;
for(int i=;i<=P;++i)
for(int j=;j<=Q;++j)
{
add(src,turn(i,j,),inf);
for(int k=;k<=R;++k)
add(turn(i,j,k),turn(i,j,k+),a[k][i][j]);
add(turn(i,j,R+),decc,inf);
}
for(int i=;i<=P;++i)
for(int j=;j<=Q;++j)
for(int k=D+;k<=R+;++k)
{
if(i>) add(turn(i,j,k),turn(i-,j,k-D),inf);
if(i<P) add(turn(i,j,k),turn(i+,j,k-D),inf);
if(j>) add(turn(i,j,k),turn(i,j-,k-D),inf);
if(j<Q) add(turn(i,j,k),turn(i,j+,k-D),inf);
}
} bool bfs()
{
for(int i=src;i<=decc;++i) lev[i]=-,cur[i]=front[i];
while(!q.empty()) q.pop();
q.push(src);
lev[src]=;
int now;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
if(lev[to[i]]==- && cap[i])
{
lev[to[i]]=lev[now]+;
if(to[i]==decc) return true;
q.push(to[i]);
}
}
return false;
} int dinic(int now,int flow)
{
if(now==decc) return flow;
int delta,rest=;
for(int &i=cur[now];i;i=nxt[i])
if(lev[to[i]]==lev[now]+ && cap[i])
{
delta=dinic(to[i],min(flow-rest,cap[i]));
if(delta)
{
rest+=delta;
cap[i]-=delta; cap[i^]+=delta;
if(rest==flow) break;
}
}
if(rest!=flow) lev[now]=-;
return rest;
} void solve()
{
int ans=;
while(bfs()) ans+=dinic(src,inf);
printf("%d",ans);
} int main()
{
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
init();
build();
solve();
}
3144: [Hnoi2013]切糕
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2143 Solved: 1165
[Submit][Status][Discuss]
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
1
6 1
6 1
2 6
2 6
Sample Output
6
HINT
最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1