题目描述
网址：https://daniu.luogu.org/problemnew/show/3227
大意：
平面上有一长方体，目标为将其切割为上下两半。
切割点为\((x,y,z)\)的点，每个点有一个不和谐值v，现在有两个要求：
- [1]任何两个平面相邻的切割点之间的高度差不能超过D
- [2]要使得最终的不和谐值最小。
求解最小的$ ∑vi $
题目解法
直接建图，化点为边。将最下面的点与S相连，最上面的与T相连。
然后跑最小割即为答案。
现在关键在于如何限制高度差不超过D。
以\((x,y,z)\)与\((x+1,y,z)\)为例。
建立\((x,y,z) —>(x+1,y,z-D)\) 与 \((x+1,y,z+D+1)—>(x,y,z+1)\)两条边
那么在割断\((x,y,z)->(x,y,z+1)\)时，就可保证\((x+1,y)\)上割的为题目所限制范围。
动手画一下就明白了。 如果割超出范围的边，S、T依旧联通。
所以用上述方法建图，然后跑最小割即可得到答案。
实现代码
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define ll long long
#define RG register
#define IL inline
#define maxn 125000
#define INF 1e16+7
using namespace std;
IL ll gi(){
RG ll date = 0, m = 1; RG char ch = 0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch = getchar();
if(ch == '-'){m = -1; ch = getchar();}
while(ch>='0' && ch<='9')
{date=date*10+ch-'0'; ch = getchar();}
return date*m;
}
ll cnt,Q,P,R,S,T,D;
ll vis[maxn],dep[maxn],head[maxn],cur[maxn];
ll mx[4] = {0,0,-1,1},my[4] = {-1,1,0,0};
struct Road { ll to,next,cap,flow; }t[20*maxn];
IL bool Bfs(){
for(RG ll i = 0; i <= T; i ++)vis[i] = 0;
dep[S] = 0; vis[S] = 1; queue<ll>Que; Que.push(S);
while(!Que.empty()){
RG ll u = Que.front(); Que.pop();
for(RG ll i = head[u]; i!= -1; i = t[i].next){
RG ll v = t[i].to;
if(!vis[v] && t[i].cap > t[i].flow){
dep[v] = dep[u] + 1;
vis[v] = true; Que.push(v);
}
}
}return vis[T];
}
int Dfs(RG ll u,RG ll Lim){
if(u == T || Lim == 0)return Lim;
RG ll flow =0,f = 0;
for(RG ll &i = cur[u]; i != -1; i = t[i].next){
RG ll v = t[i].to;
if(dep[v] == dep[u] + 1 && (f = Dfs(v,min(Lim,t[i].cap-t[i].flow))) > 0){
flow += f; Lim -= f;
t[i].flow += f; t[(i^1)].flow -= f;
if(Lim == 0)break;
}
}return flow;
}
IL int Dinic(){
RG ll Flow = 0;
while(Bfs()){
for(RG ll i = 0; i <= T; i ++)cur[i] = head[i];
Flow += Dfs(S,INF);
}return Flow;
}
IL ll Cod(RG ll z,RG ll x,RG ll y){
return z*(P*Q) + (x-1)*Q + y;
}
IL void Add(ll uu,ll vv,ll cc){
t[cnt++] = (Road){vv,head[uu],cc,0}; head[uu] = cnt - 1;
t[cnt++] = (Road){uu,head[vv],0,0}; head[vv] = cnt - 1;
}
int main(){
freopen("testdate.in","r",stdin);
P = gi(); Q = gi(); R = gi(); D = gi();
S = 0; T = R*P*Q+P*Q+1;
for(RG ll i = 0; i <= T; i ++)head[i] = -1;
for(RG ll h = 1; h <= R; h ++)
for(RG ll i = 1; i <= P; i ++)
for(RG ll j = 1; j <= Q; j ++)
Add( Cod(h,i,j) , Cod(h-1,i,j) , gi());
for(RG ll i = 1; i <= P; i ++)
for(RG ll j = 1; j <= Q; j ++)
Add(Cod(0,i,j),T,INF);
for(RG ll i = 1; i <= P; i ++)
for(RG ll j = 1; j <= Q; j ++)
Add(S,Cod(R,i,j),INF);
for(RG ll h = 1; h <= R; h ++)
for(RG ll i = 1; i <= P; i ++)
for(RG ll j = 1; j <= Q; j ++)
for(RG ll f = 0; f < 4; f ++){
RG int x = mx[f]+i,y = my[f]+j;
if(x<1||y<1||x>P||y>Q)continue;
if(h-D>=0)Add(Cod(h-D,x,y),Cod(h,i,j),INF);
if(h+D<=R)Add(Cod(h,i,j),Cod(h+D,x,y),INF);
}
RG ll Ans = Dinic(); printf("%lld",Ans);
return 0;
}