题目大意
「NEERC 2016」Mole Tunnels（BZOJ 4849）
有 $n$ 个洞，$m$ 只鼠，第 $i$ 个洞里有 $c_i$ 份食物。如果 $i > 1$，那么第 $i$ 个洞向 $\lfloor \frac{i}{2} \rfloor$ 个洞连一条无向边。对于每个 $k$，你要为前 $k$ 只鼠制定一个移动方案，使得它们各自移动到某个洞穴后，每个洞穴的鼠的数量不超过该洞中食物的数量（只算前 $k$ 只鼠）。在合法的情况下，要求鼠移动的距离总和最小，你只需输出最小的距离和。
数据范围：$n, m \le 10^5$。
思路分析
首先想到一个费用流的做法：可以将老鼠到某个洞里看作一个匹配，代价为它们在树上的距离。具体地：
- 从 $S$ 向 $i$ 连边，容量为 $i$ 号洞中的老鼠个数，花费为 $0$。
- 从 $i$ 向 $T$ 连边，容量为 $c_i$，花费为 $0$。
- 对于树上的边 $(u, v)$，从 $u$ 向 $v$ 连一条容量为 $+ \infty$，花费为 $1$ 的边，并从 $v$ 向 $u$ 也连一条容量，花费相同的边。
发现这样复杂度太高，不能通过。考虑模拟费用流的过程。对于每个点，我们记录它和它父亲在做费用流时边的状态（需要记录反向边），并维护它的子树内部最近的有食物的点。每次加入一只鼠的时候，我们暴力地向上跳，找到一个最近的点。之后，将它到这个点的路径增广，同时修改边的花费即可，具体过程可以看代码。由于保证树高 $\log n$，所以总时间复杂度为 $O(n \log n)$。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 1e5, inf = 1e9 + 1; |
5 | int n, m, ans, c[maxn + 3], w[maxn + 3][2], p[maxn + 3], dp[maxn + 3]; |
6 | |
7 | void dfs(int u) { |
8 | if (c[u]) { |
9 | dp[u] = 0, p[u] = u; |
10 | } else { |
11 | dp[u] = inf, p[u] = 0; |
12 | } |
13 | for (int i = 0, v; i < 2; i++) { |
14 | v = u * 2 + i; |
15 | if (v <= n) { |
16 | dfs(v); |
17 | if (p[v] && dp[v] + 1 < dp[u]) { |
18 | dp[u] = dp[v] + 1, p[u] = p[v]; |
19 | } |
20 | } |
21 | } |
22 | } |
23 | |
24 | void update(int u) { |
25 | if (!u) { |
26 | return; |
27 | } |
28 | if (c[u]) { |
29 | dp[u] = 0, p[u] = u; |
30 | } else { |
31 | dp[u] = inf, p[u] = 0; |
32 | } |
33 | for (int i = 0, v; i < 2; i++) { |
34 | v = u * 2 + i; |
35 | if (v <= n) { |
36 | if (p[v] && dp[v] + (w[v][0] ? -1 : 1) < dp[u]) { |
37 | dp[u] = dp[v] + (w[v][0] ? -1 : 1), p[u] = p[v]; |
38 | } |
39 | } |
40 | } |
41 | update(u >> 1); |
42 | } |
43 | |
44 | int insert(int u) { |
45 | int res = inf, pnt = 0, lca = 0; |
46 | for (int i = u, j = 0; i; j += (w[i][1] ? -1 : 1), i >>= 1) { |
47 | if (p[i] && dp[i] + j < res) { |
48 | res = dp[i] + j, pnt = p[i], lca = i; |
49 | } |
50 | } |
51 | for (int i = u; i != lca; i >>= 1) { |
52 | w[i][1] ? w[i][1]-- : w[i][0]++; |
53 | } |
54 | for (int i = pnt; i != lca; i >>= 1) { |
55 | w[i][0] ? w[i][0]-- : w[i][1]++; |
56 | } |
57 | c[pnt]--; |
58 | update(u); |
59 | update(pnt); |
60 | return res; |
61 | } |
62 | |
63 | int main() { |
64 | scanf("%d %d", &n, &m); |
65 | for (int i = 1; i <= n; i++) { |
66 | scanf("%d", &c[i]); |
67 | } |
68 | dfs(1); |
69 | for (int i = 1, t; i <= m; i++) { |
70 | scanf("%d", &t); |
71 | ans += insert(t); |
72 | printf("%d%c", ans, " \n"[i == m]); |
73 | } |
74 | return 0; |
75 | } |