@bzoj - 3144@ [Hnoi2013]切糕

╰半橙微兮° 2023-06-01 13:59 78阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

一个长 P 宽 Q 高 R 的长方体点阵，每个点 (x, y, z) 有一个权值 v(x, y, z)。  
请找到一个函数 f(x, y) 使得 1 ≤ f(x, y) ≤ R 且对于 |x - x'| + |y - y'| = 1，必须有 |f(x, y) - f(x', y')| ≤ D。  
最小化 ∑v(x, y, f(x, y))。

**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  
**Sample Output**  
6

## @solution@ ##

经典中的经典.jpg。

考虑 |f(x, y) - f(x', y')| ≤ D 可以拆成 f(x, y) ≤ f(x', y') + D 与 f(x', y') ≤ f(x, y) + D。  
于是我们只需要保证一对 (x, y) 相邻的 f 值 ≤ 它本身的 f 值 + D 即可。  
考虑上式，其实相当于规定一些点不能够共存，这使我们联想到最小割。

我们对于每一对 (x, y) 建 R 个点串成一条链，源点连链头，汇点连链尾。在这条链上割掉 (a, b) 这条边相当于令 f(x, y) = b（a 可以为源点），所以我们令 (a, b) 的容量为 v(x, y, b)，当 b 为汇点时容量为 inf。

考虑怎么用 inf 边表示我们的矛盾与共存关系。  
依上所述，假如 (x', y') 与 (x, y) 相邻，对于 (x, y) 中的第 i 个点，我们可以从 (x', y') 中的第 i + D 个点出发连一条 inf 边向 (x, y) 中的第 i 个点。  
这样的话，假如我们选中了第 i 个点（相当于割掉第 i 个点之前的边），则会出现路径 s -> (x', y') 的 i + D -> (x, y) 的 i -> t。  
因为选中 “(x, y) 的 i -> t” 这一段路径割肯定会不优（每条路径只割一条边是最优的），所以我们必然会割 “s -> (x', y') 的 i + D” 这一段，而这就完成了我们的目的。

## @accepted code@ ##

#include<cstdio> #include<queue> #include<algorithm> using namespace std; const int MAXN = 45; const int MAXV = MAXN*MAXN*MAXN; const int MAXE = 30*MAXV; const int INF = (1<<30); const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; struct FlowGraph{ struct edge{ int to, cap, flow; edge *nxt, *rev; }edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt; FlowGraph() {ecnt = &edges[0];} void addedge(int u, int v, int c) { edge *p = (++ecnt), *q = (++ecnt); p->to = v, p->cap = c, p->flow = 0; p->nxt = adj[u], adj[u] = p; q->to = u, q->cap = 0, q->flow = 0; q->nxt = adj[v], adj[v] = q; p->rev = q, q->rev = p; } int d[MAXV + 5], s, t; queue<int>que; bool relabel() { for(int i=s;i<=t;i++) d[i] = INF, cur[i] = adj[i]; d[t] = 0; que.push(t); while( !que.empty() ) { int f = que.front(); que.pop(); for(edge *p=adj[f];p;p=p->nxt) if( p->rev->cap > p->rev->flow ) if( d[f] + 1 < d[p->to] ) { d[p->to] = d[f] + 1; que.push(p->to); } } return !(d[s] == INF); } int aug(int x, int tot) { if( x == t ) return tot; int sum = 0; for(edge *&p=cur[x];p;p=p->nxt) { if( p->cap > p->flow && d[p->to] + 1 == d[x] ) { int del = aug(p->to, min(tot - sum, p->cap - p->flow)); p->flow += del, p->rev->flow -= del, sum += del; if( sum == tot ) return sum; } } return sum; } int max_flow(int _s, int _t) { s = _s, t = _t; int flow = 0; while( relabel() ) flow += aug(s, INF); return flow; } }G; int P, Q, R, D, s, t; int id[MAXN][MAXN][MAXN], cnt; int v[MAXN][MAXN][MAXN]; int main() { scanf("%d%d%d%d", &P, &Q, &R, &D); for(int i=1;i<=R;i++) for(int j=1;j<=P;j++) for(int k=1;k<=Q;k++) scanf("%d", &v[i][j][k]), id[i][j][k] = (++cnt); s = 0, t = cnt + 1; for(int i=1;i<=R;i++) for(int j=1;j<=P;j++) for(int k=1;k<=Q;k++) G.addedge(id[i-1][j][k], id[i][j][k], v[i][j][k]); for(int j=1;j<=P;j++) for(int k=1;k<=Q;k++) G.addedge(id[R][j][k], t, INF); for(int i=1;i+D<=R;i++) for(int j=1;j<=P;j++) for(int k=1;k<=Q;k++) for(int l=0;l<4;l++) { int x = j + dx[l], y = k + dy[l]; if( x < 1 || y < 1 || x > P || y > Q ) continue; G.addedge(id[i+D][x][y], id[i][j][k], INF); } printf("%d\n", G.max_flow(s, t)); }

## @details@ ##

同理，假如每个点有若干个连续的状态 1...p\[i\]，某些点对之间会有限制（比如要求两个点选择的状态编号的差的绝对值不超过 k），则可以采用类似上文的建模方法。

据说这个模型叫作切糕模型。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11396390.html