rt,代码如下:
#include <cstring>
#include <string>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <limits.h>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
using namespace std;
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)<(b)?(b):(a))
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
#define f(nm1,nm2,nm3) for(ll nm1=nm2; nm1<= nm3; nm1++)
namespace flow{
int s,t;
vector<pair<int,ll>> v[30100];
map<pair<int,int>,pair<int,int>> mp;
void addedge(int x,int y,ll w){
v[x].push_back({y,w});
v[y].push_back({x,0});
mp[{x,v[x].size()-1}]={y,v[y].size()-1};
mp[{y,v[y].size()-1}]={x,v[x].size()-1};
}
int cur[30105],dep[30105];
bool bfs(){
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(s);
dep[s]=1;
bool ok=0;
while(q.size()){
int x=q.front();
if(x==t)
ok=1;
q.pop();
for(auto y:v[x]){
if(dep[y.v1]||!y.v2)
continue;
dep[y.v1]=dep[x]+1;
q.push(y.v1);
}
}
memset(cur,0,sizeof(cur));
return ok;
}
ll dfs(int k,ll hsflow){
if(k==t)
return hsflow;
for(int i=cur[k]; i < v[k].size(); i++){
cur[k]=i;
auto y=v[k][i];
if(!y.v2||dep[k]+1!=dep[y.v1])
continue;
ll res=dfs(y.v1,min(hsflow,y.v2));
if(!res){
dep[y.v1]=0;
continue;
}
v[k][i].v2-=res;
v[mp[{k,i}].v1][mp[{k,i}].v2].v2+=res;
return res;
}
return 0;
}
ll dinic(){
ll ans=0;
while(bfs())
ans+=dfs(s,INF);
return ans;
}
}
ll val[45][45][45];
int p,q,r,d;
map<pair<int,pair<int,int>>,int> mch;
int cnt=0;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int main(){
sc("%d%d%d",&p,&q,&r);
sc("%d",&d);
flow::s=++cnt;
flow::t=++cnt;
for(int i=1; i <= r; i++){
for(int j=1; j <= p; j++){
for(int k=1; k <= q; k++){
sc("%lld",&val[j][k][i]);
mch[{j,{k,i}}]=++cnt;
}
}
}
for(int i=1; i <= p; i++){
for(int j=1; j <= q; j++){
flow::addedge(flow::s,mch[{i,{j,1}}],INF);
}
}
for(int k=1; k < r; k++){
for(int i=1; i <= p; i++){
for(int j=1; j <= q; j++){
flow::addedge(mch[{i,{j,k}}],mch[{i,{j,k+1}}],val[i][j][k]);
}
}
}
for(int i=1; i <= p; i++){
for(int j=1; j <= q; j++){
flow::addedge(mch[{i,{j,r}}],flow::t,val[i][j][r]);
}
}
for(int i=1; i <= p; i++){
for(int j=1; j <= q; j++){
for(int k=1; k <=r; k++){
if(k<=d)
continue;
for(int l=0; l <4;l++){
int xx=i+dir[l][0];
int yy=j+dir[l][1];
if(xx>=1&&xx<=p&&yy>=1&&yy<=q){
flow::addedge(mch[{i,{j,k}}],mch[{xx,{yy,k-d}}],INF);
}
}
}
}
}
cout << flow::dinic();
return 0;
}
//p3227