记录编号	494571	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2013]切糕	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.185 s
提交时间	2018-04-11 23:15:14	内存使用	1.61 MiB

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define inf (int)1e9
using namespace std;
const int maxn=65000;
struct Edge{int from,to,cap,flow;};
struct Dinic{
	int s,t,d[maxn],cur[maxn];
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vis[maxn];
	void Addedge(int from,int to,int cap){
		edges.push_back((Edge){from,to,cap,0});
		edges.push_back((Edge){to,from,0,0});
		int m=edges.size();
		G[from].push_back(m-2),G[to].push_back(m-1);
	}
	bool BFS(){
		memset(vis,0,sizeof(vis));
		queue<int>q;
		q.push(s),vis[s]=1,d[s]=0;
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<(int)G[u].size();i++){
				Edge e=edges[G[u][i]];
				if(!vis[e.to]&&e.cap>e.flow){
					vis[e.to]=1,d[e.to]=d[u]+1;q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	int DFS(int x,int v){
		if(x==t||!v)return v;
		int f,flow=0;
		for(int&i=cur[x];i<(int)G[x].size();i++){
			Edge& e=edges[G[x][i]];
			if((d[x]+1==d[e.to])&&(f=DFS(e.to,min(v,e.cap-e.flow)))){
				e.flow+=f,flow+=f,v-=f;
				edges[G[x][i]^1].flow-=f;
				if(!v)break;
			}
		}
		return flow;
	}
	int Maxflow(int a,int b){
		this->s=a,this->t=b;
		int flow=0;
		while(BFS())memset(cur,0,sizeof(cur)),flow+=DFS(s,inf);
		return flow;
	}
}A;
int P,Q,R,D;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int g(int x,int y,int z){return (z-1)*P*Q+(x-1)*Q+y;}
int main(){
	freopen("nutcake.in","r",stdin);
	freopen("nutcake.out","w",stdout);
	scanf("%d%d%d%d",&P,&Q,&R,&D);
	int v,s=0,t=P*Q*(R+1)+1;
	for(int x=1;x<=P;x++)for(int y=1;y<=Q;y++)
		A.Addedge(s,g(x,y,1),inf),A.Addedge(g(x,y,R+1),t,inf);
	for(int z=1;z<=R;z++)for(int x=1;x<=P;x++)for(int y=1;y<=Q;y++){
		scanf("%d",&v);
		A.Addedge(g(x,y,z),g(x,y,z+1),v);
		if(z-D<=0)continue;
		for(int k=0;k<4;k++){
			int xx=x+dx[k],yy=y+dy[k];
			if(xx<1||yy<1||xx>P||yy>Q)continue;
			A.Addedge(g(x,y,z),g(xx,yy,z-D),inf);
		}
	}
	int ans=A.Maxflow(s,t);
	printf("%d\n",ans);
	return 0;
}