CF536D Tavas in Kansas 题解

CF536D Tavas in Kansas

题意

给定一张 $n$ 个点 $m$ 条边的可能有自环和重边的无向连通图，每条边都有一个非负边权。
小 X 和小 Y 在这张图上玩一个游戏，在游戏中，第 $i$ 个城市有一个权值 $p_i$ 。
一开始，小 X 在城市 $s$ 中，小 Y 在城市 $t$ 中，两人各有一个得分，初始为 $0$ ，小 X 为先手，然后轮流进行操作。
当轮到某一个人时，他必须选择一个非负整数 $x$ ，以选定所有与他所在的城市的最短距离不超过 $x$ 的还未被选定过的城市，他的得分将会加上这些城市的权值。
另外，每个人每次必须能够至少选定一个城市。
当没有人可以选择时，游戏结束，得分高者获胜。
现在请你计算出，在两人都使用最佳策略的情况下，谁会获胜（或者判断为平局）。
$n \le 2 \times 10^3$ ， $m \le 10^5$ ， $|p_i| \le 10^9$ 。

题解

首先做两次 dijkstra 求出 $\operatorname{dist}(s/t, 1\dots n)$ 并离散化，值域降为 $\mathcal O(n)$ 。

由于 $\mathcal O(n^2)$ 可以接受，因此直接 dp 即可。

设 $f(P, S, T)$ 表示此时先手为 $P$ ，还剩下 $\operatorname{dist}(s, i) \ge S$ 且 $\operatorname{dist}(t, i) \ge T$ 的点 $i$ 时，先手的最大得分。

则有 $f(P, S, T) = \begin{cases} 0 & c(S, T) = 0 \\\\ \max_{c(A,T) < c(S,T)} s(S,T) - f(1,A,T) & P = 0 \\\\ \max_{c(S,B) < c(S,T)} s(S,T) - f(0,S,B) & P = 1 \end{cases}$ 要后缀 $\min$ 优化，总时间复杂度 $\mathcal O(n \log m + n^2)$ 。

实现上，可以递推出对于每个 $(S,T)$ ， $\min_{i\ge S, j \ge T, c(i,j) < c(S,T)} i/j$ 的值，然后 $f$ 值直接设为后缀 $\min$ 。

代码

const int N = 2e3 + 7;
const ll inf = 1e18;
int n, m, S, T, a[N], v[N], cs, ct, c[N][N], ns[N][N], nt[N][N];
ll ds[N], dt[N], num[N], f[2][N][N], s[N][N];
vector<pi> e[N];

inline void dij(int s, ll *d, int &c) {
	for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
	pq<pair<ll, int>> q;
	d[s] = 0, q.push(mp(0, s));
	while (q.size()) {
		int x = q.top().se;
		q.pop();
		if (v[x]) continue;
		v[x] = 1;
		for (pi o : e[x]) {
			int y = o.fi, z = o.se;
			if (d[y] > d[x] + z) d[y] = d[x] + z, q.push(mp(-d[y], y));
		}
	}
	for (int i = 1; i <= n; i++) num[i] = d[i];
	sort(num + 1, num + n + 1);
	c = unique(num + 1, num + n + 1) - (num + 1);
	for (int i = 1; i <= n; i++)
		d[i] = lower_bound(num + 1, num + c + 1, d[i]) - num;
}

int main() {
	rd(n), rd(m), rd(S), rd(T);
	for (int i = 1; i <= n; i++) rd(a[i]);
	for (int i = 1, x, y, z; i <= m; i++)
		rd(x), rd(y), rd(z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
	dij(S, ds, cs), dij(T, dt, ct);
	for (int i = 1; i <= n; i++)
		++c[ds[i]][dt[i]], s[ds[i]][dt[i]] += a[i];
	for (int i = cs; i; i--)
		for (int j = ct; j; j--) {
			s[i][j] += s[i+1][j] + s[i][j+1] - s[i+1][j+1];
			ns[i][j] = min(i == cs ? cs : ns[i+1][j], j == ct ? cs : ns[i][j+1]);
			nt[i][j] = min(i == cs ? ct : nt[i+1][j], j == ct ? ct : nt[i][j+1]);
			if (c[i][j]) ns[i][j] = i, nt[i][j] = j;
			f[0][i][j] = s[i][j] - f[1][ns[i][j]+1][j];
			f[1][i][j] = s[i][j] - f[0][i][nt[i][j]+1];
			if (i == 1 && j == 1) continue;
			f[0][i][j] = min(f[0][i][j], f[0][i][j+1]);
			f[1][i][j] = min(f[1][i][j], f[1][i+1][j]);
		}
	ll ans = s[1][1] - 2 * f[0][1][1];
	prints(ans < 0 ? "Break a heart" : (ans > 0 ? "Cry" : "Flowers"));
	return 0;
}

$\textstyle$

题意

题解

代码

评论