[HNOI2013]切糕

3144: [Hnoi2013]切糕

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2370  Solved: 1291
[Submit][Status][Discuss]

Description

Input

第一行是三个正整数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。

Output

仅包含一个整数，表示在合法基础上最小的总不和谐值。

Sample Input

2 2 2
1
6 1
6 1
2 6
2 6

Sample Output

6

HINT

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

 

考虑一下最小割，通过连inf边强制让相邻的点不割距离超过D的边。

 

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define maxn 70005
using namespace std;
const int inf=1<<30;
vector<int> g[maxn];
struct lines{
    int to,flow,cap;
}l[maxn*66];
int S,T,t=-1,d[maxn],cur[maxn];
bool v[maxn];
 
inline void add(int from,int to,int cap){
    l[++t]=(lines){to,0,cap},g[from].pb(t);
    l[++t]=(lines){from,0,0},g[to].pb(t);
}
 
inline bool BFS(){
    memset(v,0,sizeof(v));
    queue<int> q;
    q.push(S),v[S]=1,d[S]=0;
    int x; lines e;
      
    while(!q.empty()){
        x=q.front(),q.pop();
        for(int i=g[x].size()-1;i>=0;i--){
            e=l[g[x][i]];
            if(e.flow<e.cap&&!v[e.to]){
                v[e.to]=1,d[e.to]=d[x]+1;
                q.push(e.to);
            }
        }
    }
      
    return v[T];
}
  
int dfs(int x,int a){
    if(!a||x==T) return a;
    int flow=0,f,sz=g[x].size();
    for(int &i=cur[x];i<sz;i++){
        lines &e=l[g[x][i]];
        if(d[e.to]==d[x]+1&&(f=dfs(e.to,min(a,e.cap-e.flow)))){
            a-=f,flow+=f;
            e.flow+=f,l[g[x][i]^1].flow-=f;
            if(!a) break;
        }
    }
      
    return flow;
}
  
inline int max_flow(){
    int an=0;
    while(BFS()){
        memset(cur,0,sizeof(cur));
        an+=dfs(S,1<<30);
    }
    return an;
}

int n,m,w,val;
int D,id[45][45];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int main(){
	scanf("%d%d%d",&n,&m,&w);
	scanf("%d",&D),S=0,T=n*m*(w+1);
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++){
	    	id[i][j]=(i-1)*m+j;
	    	add(S,id[i][j],inf);
	    	add(id[i][j]+n*m*w,T,inf);
		}
	for(int u=1;u<=w;u++)
	    for(int i=1;i<=n;i++)
	        for(int j=1;j<=m;j++){
	        	scanf("%d",&val);
	            add(id[i][j]+(u-1)*n*m,id[i][j]+u*n*m,val);
			}
	
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	        for(int h=0,px,py;h<4;h++){
	        	px=i+dx[h],py=j+dy[h];
	        	if(id[px][py])
	        		for(int u=D;u<=w;u++) add(u*n*m+id[i][j],(u-D)*n*m+id[px][py],inf);
			}
	
	printf("%d
",max_flow());
	return 0;
}