P6122 [NEERC2016]Mole Tunnels
先考虑费用流，树上双向边，容量无限，费用为 $1$ ，源点向所有有食物的点连边，所有鼹鼠向汇点连边。发现不能一次做完所有点，需要一个一个添加，费用流不方便做此题。
考虑模拟费用流，每新加入一个点，需要找到一条源点 $\to$ 加入的点 $\to$ 汇点的一条增广路，与源点汇点连接的边是唯一的，也就是需要在树上找到一条加入的点 $\to$ 有食物的点的最短路。现在考虑如何快速找到这样的最短路，注意到这是一棵二叉树，树高只有 $\log n$ ，考虑维护 $f _ i, g _ i$ 表示点 $i$ 到其子树中有食物的点的最短路为多少、是哪个点。这样从一个点一直跳父亲，只需要 $\log n$ 次就可以确定这个点。确定点后需要将这一条路径的流量减一，反向边流量加一。
双向边以及它们的反向边的流量以及费用可以简单地用一个数组即可维护，原来的一对父子 $p, s$ 需要建边 $(p, s, inf, 1)$ 以及反向边 $(s, p, 0, -1)$ ；$(s, p, inf, 1)$ 以及反向边 $(p, s, 0, -1)$ ，无论是 $p \to s$ 还是 $s \to p$ ，都优先考虑走对方的反向边，因为反向边的费用为 $-1$ ，是更优的。这样的话，我们维护一个 $wt _ i$ 表示从 $i$ 的父亲到 $i$ 的正向边流量，当其为正的时候，表示存在边 $(p, s, inf, 1), (s, p, wt _ i, -1)$ ，父亲到儿子只能选择正向边，儿子到父亲优先选择父亲到儿子的反向边；当其为负的时候，表示存在边 $(s, p, inf, 1), (p, s, wt _ i, -1)$ ，儿子到父亲只能选择正向边，父亲到儿子优先选择反向边；当为 $0$ 的时候，那么两者都没有流量，只能选择正向边。
新加入点 $p$ 时，先不断跳父亲，找到一个父亲 $pos$ 使得路径 $p \to pos \to g _ {pos}$ 是最短路，然后修改其中的流量，对于向上的边，相当于使 wt-- ，向下的边反之。修改完路径后，需要将所有 $f _ i, g _ i$ 受到影响的点全部更新，即 $p \to pos, g _ {pos} \to pos, pos \to root$ 。
每个点完成后输出答案即可，复杂度 $O(n \log n)$ 。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar(x % 10 + '0');
}
const int N = 1e5 + 10, inf = 2e6;
int n, m, c[N], f[N << 1], g[N << 1], wt[N];
void chkmin (int &x, int &mn, int t, int k)
{
k < mn && (mn = k, x = t);
}
int cst_up (int x)
{
return wt[x] > 0 ? -1 : 1;
}
int cst_down (int x)
{
return wt[x] < 0 ? -1 : 1;
}
void update (int x)
{
f[x] = inf;
c[x] && (f[x] = 0, g[x] = x);
x << 1 <= n && (chkmin(g[x], f[x], g[x << 1], f[x << 1] + cst_down(x << 1)), 0);
(x << 1 | 1) <= n && (chkmin(g[x], f[x], g[x << 1 | 1], f[x << 1 | 1] + cst_down(x << 1 | 1)), 0);
}
int main ()
{
read(n), read(m);
for (int i = 1; i <= n; i++)
read(c[i]);
for (int i = n; i; i--)
update(i);
int res = 0;
for (int p; m; m--)
{
read(p);
int mn = inf, pos;
for (int u = p, t = 0; u; t += cst_up(u), u >>= 1)
chkmin(pos, mn, u, f[u] + t);
res += mn;
for (int u = p; u ^ pos; u >>= 1)
wt[u]--, update(u);
c[g[pos]]--;
for (int u = g[pos]; u ^ pos; u >>= 1)
wt[u]++, update(u);
for (; pos; pos >>= 1)
update(pos);
write(res), putchar(' ');
}
return 0;
}
|