BZOJ_3144_[Hnoi2013]切糕_最小割
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
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
如果没有相邻两个高度不能超过d这个限制，我们直接把这p*q*r个点拿出来求最小割即可。
S->高度为1的(v[1]) 高度为i的->高度为i+1的(v[i+1]) 高度为r的->T(inf)
现在有了限制，即我们不能割掉两个相邻的并且高度差大于d的边。
这样处理：高度为k的点向四周高度为k+d的连一条inf的边，这样我如果割两个高度差大于d的边，就还会有一条inf的通路，使得S,T连通。
限制了不能割这样的两条边。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 3050
#define M 300050
#define S (n*m+1)
#define T (n*m+2)
#define inf 100000000
#define p(i,j) ((i-1)*m+j)
int head[N],to[M],nxt[M],flow[M],cnt=1,n,m,dep[N],Q[N],l,r;
inline void add(int u,int v,int f) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f;
to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0;
}
bool bfs() {
memset(dep,0,sizeof(dep));
dep[S]=1; l=r=0; Q[r++]=S;
while(l<r) {
int x=Q[l++],i;
for(i=head[x];i;i=nxt[i]) {
if(!dep[to[i]]&&flow[i]) {
dep[to[i]]=dep[x]+1;
if(to[i]==T) return 1;
Q[r++]=to[i];
}
}
}
return 0;
}
int dfs(int x,int mf) {
if(x==T) return mf;
int nf=0,i;
for(i=head[x];i;i=nxt[i]) {
if(dep[to[i]]==dep[x]+1&&flow[i]) {
int tmp=dfs(to[i],min(mf-nf,flow[i]));
if(!tmp) dep[to[i]]=0;
nf+=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(nf==mf) break;
}
}
return nf;
}
void dinic() {
int ans=0,f;
while(bfs()) while(f=dfs(S,inf)) ans+=f;
printf("%d\n",ans);
}
char s[60];
int main() {
int A,B,i,j;
scanf("%d%d%d%d",&n,&m,&A,&B);
for(i=1;i<=n;i++) {
scanf("%s",s+1);
for(j=1;j<=m;j++) {
if(s[j]=='#') {
add(S,p(i,j),B);
}else {
add(p(i,j),T,B);
}
}
}
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
if(i>1) add(p(i,j),p(i-1,j),A);
if(i<n) add(p(i,j),p(i+1,j),A);
if(j>1) add(p(i,j),p(i,j-1),A);
if(j<m) add(p(i,j),p(i,j+1),A);
}
}
dinic();
}