题解 CF536D 【Tavas in Kansas】
xht
2020-02-09 00:53:23
# 请到博客中查看
> [CF536D Tavas in Kansas](https://codeforces.com/contest/536/problem/D)
## 题意
- 给定一张 $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$。
## 代码
```cpp
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$