题目
思路
将蛋糕割开,不就相当于切开一些边
同时又要要求值最小,所以比较明显的最小割
我们主要考虑如何将当前点的权值转换成边的容量
也很简单,将当前点向下一层的节点连一条容量为当前点的权值的边就行了
那么最后一层呢?
建一层虚层就行了。
对于D的限制
我们只需要将距离不超过D的点对之间连INF的边就行了
代码
#include<iostream>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
int p,q,r;
int d;
int a[45][45][45];
struct network_edge_dinic
{
#define maxn 724005
int s,t;
int cnt;
int cur[maxn];
int head[maxn];
int to[maxn<<1];
int val[maxn<<1];
int nxt[maxn<<1];
int d[maxn];
#undef maxn
void init()
{
cnt=1;
}
void add_edge(int u,int v,int w)
{
to[++cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
to[++cnt]=u;
val[cnt]=0;
nxt[cnt]=head[v];
head[v]=cnt;
}
int dfs(int u,int f)
{
if(u==t)
return f;
int minn=0,summ=0;
for(int& i=cur[u];i;i=nxt[i])
{
int v=to[i];
if(d[v]==d[u]+1&&val[i]>0)
{
minn=dfs(v,min(f,val[i]));
f-=minn;
val[i]-=minn;
val[i^1]+=minn;
summ+=minn;
if(!f)
break;
}
}
if(!summ)
d[u]=-1;
return summ;
}
bool bfs()
{
memset(d,-1,sizeof(d));
queue<int> q;
q.push(s);
d[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(d[v]==-1&&val[i]>0)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
if(d[t]!=-1)
return 1;
return 0;
}
int dinic(int S,int T)
{
s=S;
t=T;
int ans=0;
while(bfs())
{
for(int i=1;i<=p*q*r+2;i++)
cur[i]=head[i];
ans+=dfs(s,1e9);
}
return ans;
}
}g;
int gethash(int x,int y,int z)
{
return (z-1)*p*q+(x-1)*q+y;
}
int main()
{
g.init();
cin>>p>>q>>r>>d;
for(int i=1;i<=r;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=q;k++)
cin>>a[j][k][i];
r++;
for(int i=1;i<=p;i++)
for(int j=1;j<=q;j++)
{
g.add_edge(p*q*r+1,gethash(i,j,1),INT_MAX);
g.add_edge(gethash(i,j,r),p*q*r+2,INT_MAX);
}
for(int i=1;i<=p;i++)
for(int j=1;j<=q;j++)
for(int k=1;k<r;k++)
g.add_edge(gethash(i,j,k),gethash(i,j,k+1),a[i][j][k]);
for(int i=1;i<p;i++)
for(int j=1;j<=q;j++)
for(int k=d+1;k<=r;k++)
{
g.add_edge(gethash(i,j,k),gethash(i+1,j,k-d),INT_MAX);
g.add_edge(gethash(i+1,j,k),gethash(i,j,k-d),INT_MAX);
}
for(int i=1;i<=p;i++)
for(int j=1;j<q;j++)
for(int k=d+1;k<=r;k++)
{
g.add_edge(gethash(i,j,k),gethash(i,j+1,k-d),INT_MAX);
g.add_edge(gethash(i,j+1,k),gethash(i,j,k-d),INT_MAX);
}
cout<<g.dinic(p*q*r+1,p*q*r+2);
return 0;
}