題目描述

經過千辛萬苦小 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

---

題解

題目要求就是在一個\(n\times m\)的矩陣中填數
每個位置都是一個數軸,數軸上每一格都代表了一個數,相鄰兩點間所選擇的數軸上的位置的距離不超過\(D\)
,問將矩陣填成\(n\times m\)的最小花費
可以發現每個點的貢獻最多只能被計算一次
那么可以用最小割來解決
用\(v_{i,j,k}\)表示第\(i\)行,第\(j\)列,數軸上選擇第\(k\)個點的值
我們可以把每個位置上的數軸的相鄰點\(v_{i,j,k-1}\to v_{i,j,k}\)之間連邊,流量就是\(v_{i,j,k}\)
這樣如果選擇了數軸上的第\(k\)個點就要割掉這條邊并花費\(v_{i,j,k}\)
然后我們還需要考慮一個限制就是相鄰的點在數軸上選擇的距離不超過\(D\)
那么我們對于點\((i,j)\)，只需滿足\(f(i,j)-f(x,y)\le d\)即可
因為如果\(f(i,j) - f(x,y) < -d\)
那么在點\((x,y)\)的限制中就成了\(f(x,y)-f(i,j) > d\)
那么這顯然不滿足條件
所以只連\((i,j,k) \to (i,j,k-d)\)的邊,流量為\(INF\),表示這條限制不會被割掉
有一位\(dalao\)的圖畫的肥腸形象
盜用一下以便理解==

代碼

/* 對于光滑的限制: 只需要考慮f(i,j) - f(x,y) <= d 即可 因為如果存在 f(i,j) - f(x,y) < -d 那么換做f(x,y)的限制就成了f(x,y) - f(i.j) > d 也自然就不符合條件了*/ #include<queue> #include<cstdio> #include<cstring> #include<algorithm> const int N = 45 ; const int M = 100005 ; const int INF = 1e9 ; const int dx[] = {-1 , 0 , 1 , 0} ; const int dy[] = {0 , -1 , 0 , 1} ; using namespace std ; inline int read() {char c = getchar() ; int x = 0 , w = 1 ;while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }return x*w ; }int n , m , h , d , S , T , cnt , num = 1 ; int id[N][N][N] , val[N][N][N] , hea[M] , dep[M] ;struct E { int nxt , to , dis ; } edge[M * 10] ; inline void Insert_edge(int from , int to , int dis) {edge[++num].nxt = hea[from] ; edge[num].to = to ;edge[num].dis = dis ; hea[from] = num ; } inline void add_edge(int u , int v , int w) {Insert_edge(u , v , w) ;Insert_edge(v , u , 0) ; } inline bool bfs() {queue < int > q ; q.push(S) ;memset(dep , 0 , sizeof(dep)) ; dep[S] = 1 ;while(!q.empty()) {int u = q.front() ; q.pop() ;for(int i = hea[u] ; i ; i = edge[i].nxt) {int v = edge[i].to ; if(!dep[v] && edge[i].dis > 0) {dep[v] = dep[u] + 1 ; q.push(v) ;}}}return dep[T] ; } int dfs(int u , int dis) {if(u == T || !dis) return dis ;int sum = 0 ;for(int i = hea[u] ; i ; i = edge[i].nxt) {int v = edge[i].to ; if(dep[v] == dep[u] + 1 && edge[i].dis > 0) {int diss = dfs(v , min(dis , edge[i].dis)) ;if(diss > 0) {edge[i].dis -= diss ; edge[i ^ 1].dis += diss ;sum += diss ; dis -= diss ; if(!dis) break ;}}}if(!sum) dep[u] = -1 ; return sum ; } inline int dinic() {int ans = 0 ;while(bfs())ans += dfs(S , INF) ;return ans ; } int main() {n = read() ; m = read() ; h = read() ; d = read() ;S = 0 ; T = n * m * h + 1 ;for(int k = 1 ; k <= h ; k ++)for(int i = 1 ; i <= n ; i ++)for(int j = 1 ; j <= m ; j ++) {id[i][j][k] = ++ cnt ;val[i][j][k] = read() ;}for(int i = 1 ; i <= n ; i ++)for(int j = 1 ; j <= m ; j ++) {for(int k = 1 ; k <= h ; k ++)add_edge(id[i][j][k - 1] , id[i][j][k] , val[i][j][k]) ;add_edge(id[i][j][h] , T , INF) ;}for(int i = 1 ; i <= n ; i ++)for(int j = 1 ; j <= m ; j ++)for(int k = d + 1 ; k <= h ; k ++)for(int t = 0 , x , y ; t < 4 ; t ++) {x = i + dx[t] , y = j + dy[t] ;if(x < 1 || y < 1 || x > n || y > m) continue ;add_edge(id[i][j][k] , id[x][y][k - d] , INF) ;}printf("%d\n",dinic()) ;return 0 ; }

轉載于:https://www.cnblogs.com/beretty/p/10726344.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。