ARC098F Donation 题解

ARC098F Donation

题意

• 给定一张 $n$ 个点 $m$ 条边的无向连通图，每个点有两个属性 $a_i,b_i$。
• 一开始你有 $w$ 元，你要从某个满足 $a_s \le w$ 的节点 $s$ 开始，每次进行下列两个操作中的一个：
  • 选择一个相邻的满足 $a_v \le w$ 的节点 $v$ 移动过去。
  • 给当前所在的节点 $u$ 捐赠 $b_u$ 元，要求剩余的钱不小于 $0$ 元。
• 要求能使所有节点都被捐赠过的最小的 $w$。
• $n,m \le 10^5$。

题解

结论一：每个节点最多捐赠一次，因为捐赠更多不优。

结论二：捐赠了某个点之后不会再访问这个点，因为如果会再次访问，先捐赠了不优。

结论三：每次到达一个点 $i$ 之后，无论是否捐赠，剩余钱数应该不小于 $c_i = \max(a_i-b_i,0)$。

考虑最大的 $c_i$，设删除 $i$ 后图被分成了 $k$ 个连通块，则一定是先处理 $k-1$ 个连通块，然后在 $i$ 捐赠，然后处理最后一个连通块，并且不回到 $i$。

对于每个连通块递归的处理即可。

于是考虑借助并查集按照 $c_i$ 从小到大建树，然后树形 DP 一下即可。

总时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, m, p[N], f[N];
ll a[N], b[N], c[N], s[N], ans[N];
vi g[N], e[N];
bool v[N];

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

void dfs(int x) {
	s[x] = b[x], ans[x] = inf;
	for (int y : e[x])
		dfs(y), s[x] += s[y];
	for (int y : e[x])
		ans[x] = min(ans[x], s[x] - s[y] + max(c[x], ans[y]));
	if (ans[x] == inf) ans[x] = b[x] + c[x];
}

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++)
		rd(a[i], b[i]), c[i] = max(0ll, a[i] - b[i]), p[i] = f[i] = i;
	sort(p + 1, p + n + 1, [&](int i, int j) { return c[i] < c[j]; });
	for (int i = 1, x, y; i <= m; i++)
		rd(x, y), g[x].pb(y), g[y].pb(x);
	for (int i = 1; i <= n; i++) {
		int x = p[i];
		for (int y : g[x])
			if (v[y] && get(y) != x)
				e[x].pb(get(y)), f[get(y)] = x;
		v[x] = 1;
	}
	dfs(p[n]);
	print(ans[p[n]]);
	return 0;
}