Skip to content

S2OJ - 1912. 变异大老鼠

题解约 2.2 千字
# 动态规划 # S2OJ # 树形 DP
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

上一届警察猫局长鞠躬尽瘁，侦破大大小小案件上千件。在他的带领下，他所管辖区的犯罪率降到了历史最低点。可他也有遗憾未完成：穷凶极恶的大老鼠杨吞天至今未被抓捕归案，他也因此被迫辞职。

如今你被你的领导推到了刀山火海上，你接任当上了警察猫局长，如果不尽快逮捕杨吞天，你也难逃被撤职的命运。为了保住自己警察局长的位置，你决定动用全警局的力量全力抓捕杨吞天！

#题目描述

杨吞天是家喻户晓的变异大老鼠，他生性险恶，作恶无数。前不久，他就 XX 中学前，咬烂了一位学生的鞋子，然后逃之夭夭。你的辖区可以表示为一张带权无向图，XX 中学为 11 号结点。

你仔细研究杨吞天的案底后得出了以下结论：

  • 首先，杨吞天反侦察能力极强，他知道他走过的地方会被猫警察发现，于是他从不走回头路。
  • 其次，他深知多走一秒钟路就多一秒钟被发现的危险，因此，他提前摸清了你所属辖区的道路状况，并且只会走 11 号结点到其他结点的最短路。幸运的是，你管辖的辖区，11 号结点到其他每个结点的最短路只有一条。
  • 再次，他为了尽可能地逃离案发现场，他必须不停地走下去。也就是说，只要有相邻的结点满足以上两个要求（只走最短路，不走回头路），他就一定会移动。如果有多个结点满足，他会等概率随机地选择一个结点走去。如果没有结点满足要求，那么他就会选择逃窜到垃圾堆之中，在垃圾堆里抓鼠的难度可想而知，这也就意味着你的行动失败了。你问我为什么他不一开始就选择遁入垃圾堆，那是因为杨吞天是个变态，他乐于和猫警察玩猫鼠游戏来满足他的变态心理。

在研究清楚杨吞天的行动规律后，你决定在一些结点上布置猫警察，当杨吞天抵达这个结点时，这个结点上的警察便会逮捕杨吞天。不过杨吞天穷凶极恶，身体素质极强并且擅长使用各种凶器，他有一定的概率把这个结点上的猫警察眼睛头糊满泥巴后摆脱逮捕，警察数量越多概率越低。当他摆脱逮捕后，他会像没事发生一样按上文的方式继续行动，直至遁入垃圾堆或在之后的某个地方被逮捕。

注意，杨吞天一旦到达下一个结点，那里埋伏的猫警察会立即行动，杨吞天只有制服了那里的所有警察，才会进行下一步行动。包括 11 号结点，杨吞天只有制服了在 11 号结点埋伏的警察，才会继续移动。

你作为一个学过 OI 的警察猫局长，已经知道了你的辖区内每个点设置不同数量的猫警察成功抓捕杨吞天的概率。你需要找出最优的安排猫警察埋伏的方案，从而使得将杨吞天逮捕归案的概率最大。

#输入格式

第一行三个正整数 n,m,kn, m, k，分别表示你所管辖区的点数和边数以及你可以调动的警察数量。

接下来 mm 行，每行 33 个正整数 x,y,zx, y, z，表示有一条从 xx 到 yy 的长度为 zz 的无向边（不保证没有重边和自环）。

接下来 nn 行，每行 kk 个实数，第 ii 行第 jj 列的数 pi,jp_{i, j} 表示在编号为 ii 的结点上布置 jj 个警察埋伏，在这里抓住杨吞天的概率。注意，如果不布置警察，那么显然不可能抓到杨吞天。

#输出格式

输出一行一个实数，表示抓住杨吞天的最高概率，保留到小数点后 66 位。

#输入输出样例

样例输入 #1

4 4 2
1 2 1
1 3 2
2 4 3
3 4 1
0.01 0.1
0.5 0.8
0.5 0.8
0.7 0.9

样例输出 #1

0.600000

样例解释 #1

杨吞天在结点 11 会等概率选择前往 22 号结点或 33 号结点。如果选择前往 22 号结点，那么下一步他会选择逃往垃圾堆，因为 11 号结点已经走过了，而往 44 号结点走就不是最短路了；如果选择了 33 号结点，那么下一步他会继续往 44 号结点跑，然后逃往垃圾堆（到 44 号结点后继续往 22 号结点跑也不是最短路）。

最优警察安排是：在 22、44 号结点处各埋伏 11 名警察。这样如果杨吞天在第一步选择了 22 号结点（50%50\% 概率），那么在 22 号结点处有 50%50\% 概率被抓，50%50\% 概率逃脱后垃圾堆。如果第一步选择了 33 号结点（50%50\% 概率），这里没有警察埋伏，直接走到 44 号结点（100%100\% 概率），在这里被抓的概率是 70%70\%，所以总的概率为 50%×50%+50%×70%=60%50\% \times 50\% + 50\% \times 70\% = 60\%。

样例 #2

见选手目录下的 arrest/arrest2.in 与 arrest/arrest2.ans。

#数据范围与约定

对于所有测试点，满足 1≤n,k≤3001 \leq n, k \leq 300，1≤m≤3×1041 \leq m \leq 3 × 10^4，1≤x,y≤n1 \leq x, y \leq n，1≤z≤1061 \leq z \leq 10^6，0≤pi,j≤10 \leq p_{i,j} \leq 1，pi,j≤pi,j+1p_{i,j} \leq p_{i, j + 1}，pi,jp_{i, j} 最多只有 66 位小数。

每个子任务的具体限制见下表：

子任务编号 分值 n,k≤n, k \leq 特殊限制
11 2020 66 无
22 3030 5050 A
33 5050 300300 无

特殊性质 A：每个结点的度数不超过 33。

#思路

考虑建出一棵最小路径树（SPT），然后在上面树形 DP。

设 fi,jf_{i,j} 表示在以 ii 为根的子树中放了 jj 个警察之后，逮捕到杨吞天的最大概率。枚举当前节点放几个警察，然后转移即可。

#代码

C++
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <iterator>
#include <queue>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 305,
          M = 3e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, k, x[M], y[M], z[M];
double p[N][N], f[N][N];
std::vector<std::pair<int, int>> g[N];
int dist[N];
bool vis[N];

void dijkstra(int s) {
    std::fill(std::begin(dist), std::end(dist), INF);
    std::fill(std::begin(vis), std::end(vis), false);

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> q;

    q.emplace(0, s);
    dist[s] = 0;

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (vis[u]) continue;

        for (auto e : g[u]) {
            int v = e.first,
                w = e.second;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;

                q.emplace(dist[v], v);
            }
        }

        vis[u] = true;
    }
}

void dfs(int u) {
    if (g[u].empty()) {
        std::copy(std::begin(p[u]), std::end(p[u]), std::begin(f[u]));

        return;
    }

    for (auto e : g[u]) {
        int v = e.first;

        dfs(v);

        for (int i = k; i; i--) {
            for (int j = 1; j <= i; j++) {
                f[u][i] = std::max(f[u][i], f[u][i - j] + f[v][j] / g[u].size());
            }
        }
    }

    for (int i = k; i; i--) {
        for (int j = 1; j <= i; j++) {
            f[u][i] = std::max(f[u][i], p[u][j] + f[u][i - j] * (1.0 - p[u][j]));
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i] >> z[i];

        g[x[i]].emplace_back(y[i], z[i]);
        g[y[i]].emplace_back(x[i], z[i]);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> p[i][j];
        }
    }

    dijkstra(1);
    std::fill(std::begin(g), std::end(g), std::vector<std::pair<int, int>>());

    for (int i = 1; i <= m; i++) {
        if (dist[x[i]] + z[i] == dist[y[i]]) {
            g[x[i]].emplace_back(y[i], 0);
        }

        if (dist[y[i]] + z[i] == dist[x[i]]) {
            g[y[i]].emplace_back(x[i], 0);
        }
    }

    dfs(1);

    cout << std::fixed << std::setprecision(6) << f[1][k] << endl;

    return 0;
}