P6122 [Neerc2016]Mole Tunnels 题解

P6122 [Neerc2016]Mole Tunnels

大概是模拟费用流模板题。

考虑建出费用流的图：

• 对于每条树边 $(x,y)$，建边 $(x,y,+\infty,1),(y,x,+\infty,1)$。
• 对于每个点 $i$，建边 $(i, T, c_i, 0)$。
• 对于每只鼹鼠，依次建边 $(S, p_i, 1, 0)$。

则答案即为最小费用最大流。

由于 $n,m \le 10^5$，因此直接跑费用流肯定是不行的。

考虑模拟费用流，本质上即是一个带悔贪心。显然每次选择费用最小的洞。

在费用流中每条边有一个容量和边权，考虑直接维护这两个信息。

每次加入一个鼹鼠之后，枚举洞和鼹鼠的 LCA，找到最小费用对应的洞的位置，更新答案。

由于树上的路径最长也只有 $\mathcal O(\log n)$，因此暴力模拟费用流的更新方式更新信息即可。

在实现中，由于正向边的容量都是 $+\infty$ 边权都是 $1$，反向边的边权都是 $-1$，因此不用维护，只维护反向边的容量即可。

const int N = 1e5 + 7, inf = 1e9;
int n, m, c[N], ans;
int f[N], g[N], d[N][3];

inline void upd(int p) {
	f[p] = c[p] ? 0 : inf, g[p] = c[p] ? p : 0;
	if (ls <= n && f[p] > f[ls] + (d[p][0] ? -1 : 1))
		f[p] = f[ls] + (d[p][0] ? -1 : 1), g[p] = g[ls];
	if (rs <= n && f[p] > f[rs] + (d[p][1] ? -1 : 1))
		f[p] = f[rs] + (d[p][1] ? -1 : 1), g[p] = g[rs];
}

int main() {
	rd(n, m), rda(c, n);
	for (int i = n; i; i--) upd(i);
	for (int i = 1, x; i <= m; i++) {
		rd(x);
		int s = f[x], t = g[x], lca = x;
		int o = 0, p = x;
		while (p > 1) {
			o += d[p][2] ? -1 : 1, p >>= 1;
			if (s > o + f[p]) s = o + f[p], t = g[p], lca = p;
		}
		print(ans += s, " \n"[i==m]);
		--c[t];
		p = x;
		while (p != lca) {
			if (d[p][2]) --d[p][2];
			else ++d[p>>1][p&1];
			p >>= 1;
		}
		p = t;
		while (p != lca) {
			if (d[p>>1][p&1]) --d[p>>1][p&1];
			else ++d[p][2];
			p >>= 1;
		}
		p = x;
		while (p) upd(p), p >>= 1;
		p = t;
		while (p) upd(p), p >>= 1;
	}
	return 0;
}