Policeman and a Tree | Codeforces 868E

发表于 分类于 本文字数： 3.5k 阅读时长 ≈ 3 分钟

题目链接

一棵 \(n\) 个结点的边带权树，有一个警察初始在 \(s\) 点，速度为 \(1\)，树上分布有 \(m\) 个罪犯，速度为任意大，如果罪犯和警察在同一个结点就会被干掉，警察希望干掉所有罪犯的时间尽量短，而罪犯希望最大化这个时间，假设每个人都以最优策略行动，求这个时间。

\(1 \le n, m, w_i \le 50\)，\(w_i\) 为边权。

所有罪犯初始不在 \(s\) 点，一个结点可能会有多个罪犯。

状态设计

考虑这个过程是怎样的。

当警察在结点 \(1\) 时，由于罪犯速度任意大，但不能经过警察，所以罪犯分布在被结点 \(1\) 隔开的三个部分中，并且可以在所属部分的任意位置上，不妨假设罪犯全部分布在所有与结点 \(1\) 相邻的结点 \(2,3,4\) 上。

图上的红数字表示该结点上有多少名罪犯。

当警察从结点 \(1\) 走到结点 \(4\) 时，结点 \(4\) 上的两名罪犯就需要走到结点 \(5,6\) ，同时结点 \(2,3\) 上的两名罪犯可以一起走到结点 \(1\)。

容易想到用警察所在的结点 \(u\) 和所有与结点 \(u\) 相邻的结点上分别有多少名罪犯来表示一个状态。
但一个结点的度数是 \(O(n)\) 级别的，因此状态数爆炸。

另一个描述状态的想法是警察当前在哪条边上，这条边的两端分别有多少名罪犯。
然后状态数就减少成了 \(O(n^3)\)，非常少。

因此我们用 \(f_{i,j,k}\) 表示当前总共还剩 \(i\) 名罪犯，警察刚走上 \(j = u \rightarrow v\) 这条有向边（警察和 \(u\) 的距离忽略不计），结点 \(v\) 上有 \(k\) 名罪犯。

转移

假设当前总共还剩 \(i\) 名罪犯，警察在有向边 \(j = u \rightarrow v\) 上，边权为 \(w\)，结点 \(v\) 上有 \(k\) 名罪犯。

如果结点 \(v\) 是叶子结点，显然 \[ f_{i,j,k}=f_{i-k,\bar j,i-k} + w \] 其中 \(\bar j\) 是 \(j\) 的反向边。

另一种情况：

结点 \(4\) 上的 \(k\) 名罪犯必须要分为两波，其中 \(a\) 名跑到了结点 \(5\)，\(b\) 名跑到了结点 \(6\)。
警察会下一步会在 \(4 \rightarrow 5\) 和 \(4 \rightarrow 6\) 中选择较优的一条有向边。

罪犯为了最大化时间： \[ f_{i,1 \rightarrow 4,k} = \max_{a+b=k}\min \lbrace f_{i,4 \rightarrow 5,a},f_{i,4 \rightarrow 6,b}\rbrace + w \] 一般地，设结点 \(v\) 除 \(u\) 以外的相邻点分别为 \(a_1,a_2,a_3,\cdots,a_d\)，则转移方程为： \[ f_{i,j,k}=\max_{c_1+c_2+\cdots+c_d=k}\min_{s=1}^df_{i,v \rightarrow a_s,c_s} + w \] 下面给出一种复杂度比较优秀的贪心算法实现第二种转移：

引理：若求 \(f_{i,j,k}\) 时的决策为 \(c_1,c_2,\cdots,c_d\)。
那么求 \(f_{i,j,k+1}\) 时的决策 \(\bar c_1,\bar c_2,\cdots,\bar c_d\) 一定是在 \(c_1,c_2,\cdots,c_d\) 中的某个数 \(+1\) 得到的。
并且 \(+1\) 的这个 \(c_x\) 满足 \[ f_{i,v \rightarrow a_x,c_x+1}=\max_{s=1}^df_{i,v \rightarrow a_s,c_s+1} \] 证明：首先在总人数和位置相同的情况下，警察追的人越多，剩下的时间就越短。
故 \(f_{i,j,0} \ge f_{i,j,1} \ge f_{i,j,2} \ge \cdots \ge f_{i,j,i}\)。

考虑 \[ \forall x \le f_{i,j,k}\exists c_1,c_2,\cdots,c_d,\\\\f_{i,v \rightarrow a_1,c_1} \ge x\\\\f_{i,v \rightarrow a_2,c_2} \ge x\\\\\cdots\\\\f_{i,v \rightarrow a_d,c_d} \ge x \] 由二分答案算法的 check 函数可知：若 \(m_i\) 是 \(f_{i,v \rightarrow a_i}\) 数列中最后一个大于等于 \(x\) 的位置，
则 \(m_1+m_2+\cdots+m_d \ge k\)。

而以这种决策的构造方式，一定有 \(c_1 \le m_1,c_2 \le m_2, \cdots, c_d \le m_d\)，因此通过该决策得到的值一定不劣于 \(x\)。

因此可以用一个大根堆维护那个 \(x\)，可以在 \(O(n\log n)\) 的时间同时求出 \(f_{i,j,0},f_{i,j,1},\cdots,f_{i,j,i}\)。

复杂度 \(O(n^3\log n)\)，标算的复杂度是 \(O(n^5)\) 的。

然而由于常数巨大，最小的点要 \(15\) ms，最大的点要 \(30\) ms。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
const int N = 55, Inf = 1e9;
int n, s, m, ev[N * 2], ew[N * 2], cnt[N], deg[N];
vector <int> G[N];
int f[N][N * 2][N];
void solve(int, int);
int dp(int i, int j, int k) {
    if(!f[i][j][k]) solve(i, j);
    return f[i][j][k];
}
struct node {
    int i, e, c;
    int val()const { return c < i ? dp(i, e, c + 1) : 0; }
    bool operator <(const node& b)const { return val() < b.val(); }
};
void solve(int i, int j) {
    f[i][j][0] = Inf;
    if(deg[ev[j]] == 1)
        rep(k, 1, i) f[i][j][k] = k < i ? dp(i - k, j ^ 1, i - k) + ew[j] : ew[j];
    else {
        priority_queue <node> q;
        for(int e : G[ev[j]]) if(e ^ j ^ 1) q.push({ i, e, 0 });
        rep(k, 1, i) {
            node x = q.top(); q.pop();
            f[i][j][k] = min(f[i][j][k - 1], x.val() + ew[j]);
            x.c++, q.push(x);
        }
    }
}
int dfs(int u, int fa) {
    int res = cnt[u];
    for(int e : G[u]) if(ev[e] ^ fa) res += dfs(ev[e], u);
    return res;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    int u, v, w;
    rep(i, 2, n) {
        int a = i * 2, b = a + 1;
        cin >> u >> v >> w, deg[ev[a] = v]++, deg[ev[b] = u]++, ew[a] = ew[b] = w;
        G[u].push_back(a), G[v].push_back(b);
    }
    cin >> s >> m;
    rep(i, 1, m) cin >> u, cnt[u]++;
    int ans = Inf;
    for(int e : G[s]) ans = min(ans, dp(m, e, dfs(ev[e], s)));
    cout << ans;
    return 0;
}