【BZOJ3144】[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
題解：APIO上學到了這種建圖方法，趕緊%一發
做切糕的方法？先不考慮D的限制，那么原題就是無腦最小割，圖大概長這樣(只考慮兩個縱軸)
但如果加上這條限制，我們該怎么做？這里先給出結論，假設D=1，從7->2連一條∞的邊，從3->6連一條∞的邊（其余同理），原圖變成了這樣
（畫圖軟件有點尷尬~）
發現如果這樣連邊，我們就可以防止(1,2)與(7,8)同時被割掉，因為就算割掉這兩條邊，S仍然可以通過5-6-3-4與T聯通，所以只能割別的邊
廣東切糕。一開始我比較懶，省略了S->1,4->T這兩條長度為∞的邊，結果狂WA不止，后來發現R可以等于1。。。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define P(A,B,C) ((C-1)*n*m+(B-1)*n+A)
using namespace std;
const int maxm=1000000;
const int maxn=100010;
queue<int> q;
int n,m,h,S,T,D,cnt,ans;
int to[maxm],next[maxm],val[maxm],head[maxn],d[maxn];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int rd()
{int ret=0,f=1; char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();return ret*f;
}
int bfs()
{memset(d,0,sizeof(d));while(!q.empty()) q.pop();int i,u;d[S]=1,q.push(S);while(!q.empty()){u=q.front(),q.pop();for(i=head[u];i!=-1;i=next[i]){if(!d[to[i]]&&val[i]){d[to[i]]=d[u]+1;if(to[i]==T) return 1;q.push(to[i]);}}}return 0;
}
int dfs(int x,int mf)
{if(x==T) return mf;int i,k,temp=mf;for(i=head[x];i!=-1;i=next[i]){if(d[to[i]]==d[x]+1&&val[i]){k=dfs(to[i],min(temp,val[i]));if(!k) d[to[i]]=0;val[i]-=k,val[i^1]+=k,temp-=k;if(!temp) break;}}return mf-temp;
}
void add(int a,int b,int c)
{to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
int main()
{n=rd(),m=rd(),h=rd(),D=rd();memset(head,-1,sizeof(head));int i,j,k,l;S=0,T=n*m*h+1;for(k=1;k<=h;k++){for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(k==1) add(S,P(i,j,k),rd());else add(P(i,j,k-1),P(i,j,k),rd());if(k==h) add(P(i,j,k),T,1<<30);if(k>D) for(l=0;l<4;l++) if(i+dx[l]&&i+dx[l]<=n&&j+dy[l]&&j+dy[l]<=m)add(P(i,j,k),P(i+dx[l],j+dy[l],k-D),1<<30);}}}while(bfs()) ans+=dfs(S,1<<30);printf("%d",ans);return 0;
}?
