Visits: 214

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$