3144: [Hnoi2013]切糕

Description

Input

第一行是三個(gè)正整數(shù)P,Q,R，表示切糕的長P、 寬Q、高R。第二行有一個(gè)非負(fù)整數(shù)D，表示光滑性要求。接下來是R個(gè)P行Q列的矩陣，第z個(gè) 矩陣的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。?
100%的數(shù)據(jù)滿足P,Q,R≤40，0≤D≤R，且給出的所有的不和諧值不超過1000。

Output

僅包含一個(gè)整數(shù)，表示在合法基礎(chǔ)上最小的總不和諧值。

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

---

?

　　恩。有個(gè)同學(xué)問我，為什么連幾條inf就能保證割邊在范圍之內(nèi)？我一下子語塞。過了很久才給了他答復(fù)，他一下子歡喜極了。

　　另外，需關(guān)注題意。我本來連了8個(gè)方向，居然還懵了許久。

　　對了，這是他的內(nèi)容：

　　這道題顯然是一個(gè)網(wǎng)絡(luò)流，我們?nèi)绻豢紤]每次要切的相鄰的范圍的地方的話，直接從每一豎列的下一層往上一層連邊，大概是這么個(gè)效果

　　對于切糕中的點(diǎn)，我們以虛線的所示方法連邊，然后兩邊以INF的邊連S和T，顯然跑一邊最小割就可以了，然而現(xiàn)在我們還要解決每次切的相鄰的范圍在d之內(nèi)…這個(gè)對于我這個(gè)垃圾來說…簡直是難題！…然后我們可以這樣連?

　　我們從上往下，建INF的邊，具體操作是如果可以就向周圍的下面的豎直坐標(biāo)相差為d的點(diǎn)建邊，這樣一來為什么就可以保證割的邊在范圍之內(nèi)呢？我們看上面的圖，箭頭為正向邊的方向，假如圖中的A部分被我們割掉了，現(xiàn)在如何才能保證左側(cè)割掉的邊一定在左側(cè)的D區(qū)域呢？首先我們感性認(rèn)知一下，現(xiàn)在還存在的路是C-D-B中間進(jìn)過兩條INF的邊，還有一條路可以增廣，也就是F-D-E這條路，D同時(shí)在這兩條路里，如果只割一次，那么只能割D

　　下一步我們看來思考為什么在兩條路中各割一條會比在D中割一條不優(yōu)…可能是我太智障了，我思考這個(gè)圖思考了好久233，其實(shí)道理很簡單啊，觀察這張圖，如果我們割掉三條長度為1的邊，我們能把圖增廣完嘛？明顯不是最小割嘛，割都沒割，這里還有一條路嘛

　　也就是說，你割外面的邊而不割藍(lán)色部分的邊，你割都沒割到要點(diǎn)，反而多花費(fèi)了，并且還是有路（并且改路的最大流沒有減少）可以通過去，也就是說圖上還有一條經(jīng)過藍(lán)色邊的路徑可以被割，并且在你割不在藍(lán)色路徑上的邊之后并沒有對這條還可以增廣的路造成影響?

　　這道題由朱爺分享，代碼如下：

1 /************************************************************** 2 Problem: 3144 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:1236 ms 7 Memory:17652 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 template<class T>inline void readin(T &res) { 15 static char ch;T flag=1; 16 while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1; 17 res=ch-48;while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag; 18 } 19 20 const int N = 100100; 21 const int M = 1000010; 22 const int inf = 0x3f3f3f3f; 23 const int dx[] = {-1,1,0,0}; 24 const int dy[] = {0,0,-1,1}; 25 struct Edge {int v, upre, cap, flow;}g[M]; 26 int head[N], ne=-1; 27 inline void adde(int u,int v,int cap) { 28 g[++ne]=(Edge){v,head[u],cap,0};head[u]=ne; 29 g[++ne]=(Edge){u,head[v],0,0};head[v]=ne; 30 } 31 32 #include <queue> 33 std::queue<int> q; 34 int n, m, H, dlt, x, s, t, d[N], cur[N]; 35 bool BFS() { 36 memset(d,0,sizeof(d)); 37 while(!q.empty()) q.pop(); 38 q.push(s);d[s]=1; 39 while(!q.empty()) { 40 int u=q.front();q.pop(); 41 for( int i = head[u]; i!=-1; i = g[i].upre ) { 42 int v=g[i].v; 43 if(g[i].cap>g[i].flow&&!d[v]) {q.push(v);d[v]=d[u]+1;} 44 } 45 } 46 return d[t]!=0; 47 } 48 int DFS(int u,int a) { 49 if(u==t||a==0) return a; 50 int flow=0, f; 51 for( int &i = cur[u]; i!=-1; i = g[i].upre ) { 52 int v=g[i].v; 53 if(d[v]==d[u]+1&&(f=DFS(v,std::min(a,g[i].cap-g[i].flow)))>0) { 54 flow+=f;a-=f; 55 g[i].flow+=f;g[i^1].flow-=f; 56 if(a==0) break; 57 } 58 } 59 if(flow==0) d[u]=0; 60 return flow; 61 } 62 int maxflow() { 63 int flow=0; 64 while(BFS()) { 65 memcpy(cur,head,sizeof(head)); 66 flow+=DFS(s,inf); 67 } 68 printf("%d\n",flow); 69 } 70 inline int pos(int i,int j,int h) {return (h-1)*n*m+(i-1)*m+j;} 71 int main() { 72 memset(head,-1,sizeof(head)); 73 readin(n);readin(m);readin(H);readin(dlt);s=0;t=66000; 74 for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ) adde(s,pos(i,j,1),inf), adde(pos(i,j,H+1),t,inf); 75 for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ) for( int h = 1; h <= H+1; h++ ) if(h+dlt<=H+1) 76 for( int k = 0; k < 4; k++ ) if(1<=i+dx[k]&&i+dx[k]<=n&&1<=j+dy[k]&&j+dy[k]<=m) adde(pos(i+dx[k],j+dy[k],h+dlt),pos(i,j,h),inf); 77 for( int h = 1; h <= H; h++ ) for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ) readin(x),adde(pos(i,j,h),pos(i,j,h+1),x); 78 maxflow(); 79 return 0; 80 } 81 dinic最小割建圖（1236 ms 17652 kb）

　　對了，其中最后一層可以壓縮。

1 /************************************************************** 2 Problem: 3144 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:1112 ms 7 Memory:17652 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 template<class T>inline void readin(T &res) { 15 static char ch;T flag=1; 16 while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1; 17 res=ch-48;while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag; 18 } 19 20 const int N = 100100; 21 const int M = 1000010; 22 const int inf = 0x3f3f3f3f; 23 const int dx[] = {-1,1,0,0}; 24 const int dy[] = {0,0,-1,1}; 25 struct Edge {int v, upre, cap, flow;}g[M]; 26 int head[N], ne=-1; 27 inline void adde(int u,int v,int cap) { 28 g[++ne]=(Edge){v,head[u],cap,0};head[u]=ne; 29 g[++ne]=(Edge){u,head[v],0,0};head[v]=ne; 30 } 31 32 #include <queue> 33 std::queue<int> q; 34 int n, m, H, dlt, x, s, t, d[N], cur[N]; 35 bool BFS() { 36 memset(d,0,sizeof(d)); 37 while(!q.empty()) q.pop(); 38 q.push(s);d[s]=1; 39 while(!q.empty()) { 40 int u=q.front();q.pop(); 41 for( int i = head[u]; i!=-1; i = g[i].upre ) { 42 int v=g[i].v; 43 if(g[i].cap>g[i].flow&&!d[v]) {q.push(v);d[v]=d[u]+1;} 44 } 45 } 46 return d[t]!=0; 47 } 48 int DFS(int u,int a) { 49 if(u==t||a==0) return a; 50 int flow=0, f; 51 for( int &i = cur[u]; i!=-1; i = g[i].upre ) { 52 int v=g[i].v; 53 if(d[v]==d[u]+1&&(f=DFS(v,std::min(a,g[i].cap-g[i].flow)))>0) { 54 flow+=f;a-=f; 55 g[i].flow+=f;g[i^1].flow-=f; 56 if(a==0) break; 57 } 58 } 59 if(flow==0) d[u]=0; 60 return flow; 61 } 62 int maxflow() { 63 int flow=0; 64 while(BFS()) { 65 memcpy(cur,head,sizeof(head)); 66 flow+=DFS(s,inf); 67 } 68 printf("%d\n",flow); 69 } 70 inline int pos(int i,int j,int h) {if(h==H+1) return t;return (h-1)*n*m+(i-1)*m+j;} 71 int main() { 72 memset(head,-1,sizeof(head)); 73 readin(n);readin(m);readin(H);readin(dlt);s=0;t=66000; 74 for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ) adde(s,pos(i,j,1),inf); 75 for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ) for( int h = 1; h <= H+1; h++ ) if(h+dlt<=H+1) 76 for( int k = 0; k < 4; k++ ) if(1<=i+dx[k]&&i+dx[k]<=n&&1<=j+dy[k]&&j+dy[k]<=m) adde(pos(i+dx[k],j+dy[k],h+dlt),pos(i,j,h),inf); 77 for( int h = 1; h <= H; h++ ) for( int i = 1; i <= n; i++ ) for( int j = 1; j <= m; j++ ) readin(x),adde(pos(i,j,h),pos(i,j,h+1),x); 78 maxflow(); 79 return 0; 80 } 81 dinic最小割建圖（1112 ms 17652 kb）

?

轉(zhuǎn)載于:https://www.cnblogs.com/Doggu/p/BZOJ3144.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3144 [Hnoi2013]切糕的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。