NC20101. [HNOI2013]切糕
描述
经过千辛万苦小 A 得到了一块切糕，切糕的形状是长方体，小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑，小 A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。
出于简便考虑，我们将切糕视作一个长 P、宽 Q、高 R 的长方体点阵。我们将位于第 z层中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z)，它有一个非负的不和谐值 v(x,y,z)。一个合法的切面满足以下两个条件：
与每个纵轴(一共有 P*Q 个纵轴)有且仅有一个交点。即切面是一个函数 f(x,y)，对于所有 1≤x≤P, 1≤y≤Q,我们需指定一个切割点 f(x,y),且 1≤f(x,y)≤R。
切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的 1≤x,x’≤P 和 1≤y,y’≤Q，若|x-x’|+|y-y’|=1，则|f(x,y)-f(x’,y’)| ≤D，其中 D 是给定的一个非负整数。 可能有许多切面f 满足上面的条件，小A 希望找出总的切割点上的不和谐值最小的那个。
输入描述
第一行是三个正整数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。
输出描述
仅包含一个整数，表示在合法基础上最小的总不和谐值。
示例1
输入:
2 2 2 1 6 1 6 1 2 6 2 6
输出:
6
C++11(clang++ 3.9) 解法, 执行用时: 81ms, 内存消耗: 10460K, 提交时间: 2019-03-16 10:39:48
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=1000010,M=2000010,Inf=1e9+10;
int s,t;
class Graph{
private:
int front[N],nxt[M<<1],to[M<<1],w[M<<1],cnt,dep[N],cur[N];
bool bfs(){
queue<int >Q;while(!Q.empty())Q.pop();
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=front[u];i!=-1;i=nxt[i]){
int v=to[i];
if(!dep[v] && w[i]){
dep[v]=dep[u]+1;Q.push(v);
}
}
}
return dep[t];
}
int dfs(int u,int Flow){
if(u==t || !Flow)return Flow;
for(int &i=cur[u];i!=-1;i=nxt[i]){
int v=to[i];
if(dep[v]==dep[u]+1 && w[i]){
int di=dfs(v,min(Flow,w[i]));
if(di){
w[i]-=di;w[i^1]+=di;
return di;
}
}
}
return 0;
}
void add(int u,int v,int val){to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;cnt++;}
public:
void Add(int u,int v,int val)
{
add(u,v,val);add(v,u,0);
}
void init(){memset(front,-1,sizeof(front));cnt=0;}
int Dinic(){
int flow=0;
while(bfs()){
for(int i=0;i<=t;i++)cur[i]=front[i];
while(int d=dfs(s,Inf)){
flow+=d;
}
}
return flow;
}
}MaxFlow;
int p,q,r,v[45][45][45],d;
int wa[4]={0,0,1,-1},lk[4]={1,-1,0,0};
int id(int x,int y,int z)
{
if(!z)return 0;
return (z-1)*p*q+(x-1)*q+y;
}
void build()
{
for(int i=1;i<=p;i++)
for(int j=1;j<=q;j++)
{
for(int k=1;k<=r;k++)
{
MaxFlow.Add(id(i,j,k-1),id(i,j,k),v[i][j][k]);
if(k>d)
for(int f=0;f<4;f++)
{
int xx=i+wa[f],yy=j+lk[f];
if(xx<1 || xx>p || yy<1 || yy>q)continue;
MaxFlow.Add(id(i,j,k),id(xx,yy,k-d),Inf);
}
}
MaxFlow.Add(id(i,j,r),t,Inf);
}
}
int main()
{
MaxFlow.init();
p=gi();q=gi();r=gi();d=gi();t=p*q*r+1;
for(int i=1;i<=r;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=q;k++)
v[j][k][i]=gi();
build();
printf("%d\n",MaxFlow.Dinic());
return 0;
}
C++14(g++5.4) 解法, 执行用时: 368ms, 内存消耗: 4836K, 提交时间: 2019-10-29 22:18:52
// luogu-judger-enable-o2
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=40+5;
const int INF=0x3f3f3f3f;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
int P,Q,R,D,s,t;
int v[N][N][N];
int g[N][N][N],tot=0;
struct Edge { int v,w,nxt; };
Edge e[1000000];
int head[250000];
inline void addEdge(int u,int v,int w) {
static int cnt=0;
e[cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt++;
e[cnt].v=u,e[cnt].w=0,e[cnt].nxt=head[v],head[v]=cnt++;
}
int level[250000];
inline int bfs() {
memset(level,0,sizeof(level));
queue<int> Q; Q.push(s); level[s]=1;
while (!Q.empty()) {
int u=Q.front(); Q.pop();
for (re int i=head[u];i!=-1;i=e[i].nxt) {
int v=e[i].v;
if (e[i].w&&!level[v]) level[v]=level[u]+1,Q.push(v);
}
}
return level[t]!=0;
}
inline int dfs(int u,int cpflow) {
if (u==t) return cpflow;
int addflow=0;
for (re int i=head[u];i!=-1;i=e[i].nxt) {
int v=e[i].v;
if (e[i].w&&level[v]==level[u]+1) {
int tmpadd=dfs(v,min(cpflow-addflow,e[i].w));
e[i].w-=tmpadd,e[i^1].w+=tmpadd;
addflow+=tmpadd;
}
}
if (!addflow) level[u]=0;
return addflow;
}
inline int dinic() {
int maxflow=0;
while (bfs()) maxflow+=dfs(s,INF);
return maxflow;
}
int main() {
memset(head,-1,sizeof(head));
P=read(),Q=read(),R=read(),D=read();
for (re int k=1;k<=R;++k)
for (re int i=1;i<=P;++i)
for (re int j=1;j<=Q;++j)
v[i][j][k]=read();
for (re int i=1;i<=P;++i)
for (re int j=1;j<=Q;++j)
for (re int k=1;k<=R+1;++k)
g[i][j][k]=++tot;
s=0,t=tot+1;
for (re int i=1;i<=P;++i)
for (re int j=1;j<=Q;++j) {
addEdge(s,g[i][j][1],INF);
addEdge(g[i][j][R+1],t,INF);
}
for (re int i=1;i<=P;++i)
for (re int j=1;j<=Q;++j)
for (re int k=1;k<=R;++k)
addEdge(g[i][j][k],g[i][j][k+1],v[i][j][k]);
for (re int i=1;i<=P;++i)
for (re int j=1;j<=Q;++j)
for (re int d=0;d<4;++d) {
int x=i+dx[d],y=j+dy[d];
if (x<1||x>P||y<1||y>Q) continue;
for (re int k=D+1;k<=R+1;++k)
addEdge(g[i][j][k],g[x][y][k-D],INF);
}
printf("%d\n",dinic());
return 0;
}