題目描述 經過千辛萬苦小 A 得到了一塊切糕，切糕的形狀是長方體，小 A 打算攔腰將切糕切成兩半分給小 B。出於美觀考慮，小 A 希望切麵能儘量光滑且和諧。於是她找到你，希望你能幫她找出最好的切割方案。 出於簡便考慮，我們將切糕視作一個長 P、寬 Q、高 R 的長方體點陣。我們將位於第 z層中第 x ...
題目描述
經過千辛萬苦小 A 得到了一塊切糕，切糕的形狀是長方體，小 A 打算攔腰將切糕切成兩半分給小 B。出於美觀考慮，小 A 希望切麵能儘量光滑且和諧。於是她找到你，希望你能幫她找出最好的切割方案。
出於簡便考慮，我們將切糕視作一個長 P、寬 Q、高 R 的長方體點陣。我們將位於第 z層中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的點稱為(x,y,z)，它有一個非負的不和諧值 v(x,y,z)。一個合法的切麵滿足以下兩個條件：
-
與每個縱軸(一共有 P*Q 個縱軸)有且僅有一個交點。即切麵是一個函數 f(x,y)，對於所有 1≤x≤P, 1≤y≤Q,我們需指定一個切割點 f(x,y),且 1≤f(x,y)≤R。
- 切麵需要滿足一定的光滑性要求，即相鄰縱軸上的切割點不能相距太遠。對於所有的 1≤x,x’≤P 和 1≤y,y’≤Q，若|x-x’|+|y-y’|=1，則|f(x,y)-f(x’,y’)| ≤D，其中 D 是給定的一個非負整數。 可能有許多切麵f 滿足上面的條件，小A 希望找出總的切割點上的不和諧值最小的那個。
輸入輸出格式
輸入格式：
第一行是三個正整數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。
輸出格式：
僅包含一個整數，表示在合法基礎上最小的總不和諧值。
輸入輸出樣例
輸入樣例#1：2 2 2 1 6 1 6 1 2 6 2 6輸出樣例#1：
6
說明
最佳切麵的f為f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1
我們將點轉化成邊，那麼選點就等於割邊，第一個條件滿足
對於第二個條件我們可以用一些inf的邊來"屏蔽"那些不能割的邊，從z向"相鄰的"路徑的z-d號點連inf的邊（如上圖）這樣做之後，如果刪了這條邊，我們還可以通過這些橋梁，從相鄰的路徑的一段[z-d,z+d]繞過，所以割那些邊就沒有意義了
從而實現必須割[z-d,z+d]的目的
來源：洛谷題解
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=200001; 8 const int INF = 1e8; 9 inline void read(int &n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 13 while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();} 14 n=flag==1?-x:x; 15 } 16 int n,m,s,t; 17 struct node 18 { 19 int u,v,flow,nxt; 20 }edge[MAXN]; 21 int head[MAXN]; 22 int cur[MAXN]; 23 int num=0; 24 int deep[MAXN]; 25 int tot=0; 26 void add_edge(int x,int y,int z) 27 { 28 edge[num].u=x; 29 edge[num].v=y; 30 edge[num].flow=z; 31 edge[num].nxt=head[x]; 32 head[x]=num++; 33 } 34 void add(int x,int y,int z) 35 { 36 add_edge(x,y,z); 37 add_edge(y,x,0); 38 } 39 bool BFS() 40 { 41 memset(deep,0,sizeof(deep)); 42 deep[s]=1; 43 queue<int>q; 44 q.push(s); 45 while(q.size()!=0) 46 { 47 int p=q.front(); 48 q.pop(); 49 for(int i=head[p];i!=-1;i=edge[i].nxt) 50 if(!deep[edge[i].v]&&edge[i].flow) 51 deep[edge[i].v]=deep[edge[i].u]+1, 52 q.push(edge[i].v); 53 } 54 return deep[t]; 55 56 } 57 int DFS(int now,int nowflow) 58 { 59 if(now==t||nowflow<=0) 60 return nowflow; 61 int totflow=0; 62 for(int &i=cur[now];i!=-1;i=edge[i].nxt) 63 { 64 if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow) 65 { 66 int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow)); 67 edge[i].flow-=canflow; 68 edge[i^1].flow+=canflow; 69 totflow+=canflow; 70 nowflow-=canflow; 71 if(nowflow<=0) 72 break; 73 } 74 75 } 76 return totflow; 77 } 78 void Dinic() 79 { 80 int ans=0; 81 while(BFS()) 82 { 83 memcpy(cur,head,MAXN); 84 ans+=DFS(s,1e8); 85 } 86 printf("%d",ans); 87 } 88 int a[41][41][41]; 89 int cnt=0; 90 int xx[5]={-1,+1,0,0}; 91 int yy[5]={0,0,-1,+1}; 92 int main() 93 { 94 memset(head,-1,sizeof(head)); 95 int P,Q,R,D; 96 read(P);read(Q);read(R);read(D); 97 for(int i=1;i<=R+1;i++) 98 for(int j=1;j<=P;j++) 99 for(int k=1;k<=Q;k++) 100 a[i][j][k]=++cnt; 101 s=0;t=cnt+1; 102 for(int i=1;i<=P;i++) 103 for(int j=1;j<=Q;j++) 104 { 105 add(s,a[1][i][j],INF); 106 add(a[R+1][i][j],t,INF);//上下界 107 } 108 for(int i=1;i<=R;i++) 109 for(int j=1;j<=P;j++) 110 for(int k=1;k<=Q;k++) 111 { 112 int p;read(p); 113 add(a[i][j][k],a[i+1][j][k],p); 114 }// 連邊 115 for(int i=D+1;i<=R;i++) 116 for(int j=1;j<=P;j++) 117 for(int k=1;k<=Q;k++) 118 for(int m=0;m<4;m++) 119 if(a[i-D][j+xx[m]][k+yy[m]]>0) 120 add(a[i][j][k],a[i-D][j+xx[m]][k+yy[m]],INF); 121 //for(int i=1;i<=num-1;i++) 122 //printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].flow); 123 Dinic(); 124 return 0; 125 }
