首先跑一遍单源最短路，只保留最短路上的边，发现是一棵树。
于是显然的树形 DP 套路。
设 \(f_{i,j}\) 表示 FB 从 \(i\) 出发，以 \(i\) 为根的子树总共有 \(j\) 个 Labmem，抓捕到 FB 的最大概率。
转移比较显然，对于每个 \(i,j\)，枚举 \(i\) 上放的 Labmem 个数，并对儿子构成的子树做背包。
注意，我们不需要对于每个 \(i,j\) 都做背包，因为背包跟 \(j\) 没有关，所以对于 \(i\) 做即可。
复杂度 \(O(n \cdot s^2)\)。
代码： 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
using namespace std;
const int N = 200;
const int S = 200;
const int M = 2e4;
int n,m,s;
double rate[N + 5][S + 5];
int to[(M << 1) + 5],pre[(M << 1) + 5],val[(M << 1) + 5],first[N + 5];
inline void add(int u,int v,int w)
{
static int tot = 0;
to[++tot] = v;
val[tot] = w;
pre[tot] = first[u];
first[u] = tot;
}
int dis[N + 5],vis[N + 5],q[N * M + 5],head,tail;
double f[N + 5][S + 5],g[N + 5][S + 5];
void dfs(int p)
{
for(register int i = first[p];i;i = pre[i])
if(dis[p] + val[i] == dis[to[i]])
dfs(to[i]);
int w = 0;
memset(g,0,sizeof g);
for(register int i = first[p];i;i = pre[i])
if(dis[p] + val[i] == dis[to[i]])
{
++w;
for(register int j = 0;j <= s;++j)
for(register int k = j;~k;--k)
g[w][j] = max(g[w][j],g[w - 1][j - k] + f[to[i]][k]);
}
for(register int i = 0;i <= s;++i)
for(register int j = 0;j <= i;++j)
{
double cur = rate[p][j];
if(w)
cur += (1 - rate[p][j]) * (1.0 / w) * g[w][i - j];
f[p][i] = max(f[p][i],cur);
}
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,w;
for(register int i = 1;i <= m;++i)
scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
memset(dis,0x3f,sizeof dis);
dis[1] = 0,vis[q[++tail] = 1] = 1;
while(head < tail)
{
int p = q[++head];
vis[p] = 0;
for(register int i = first[p];i;i = pre[i])
if(dis[to[i]] > dis[p] + val[i])
{
dis[to[i]] = dis[p] + val[i];
if(!vis[to[i]])
vis[to[i]] = 1,q[++tail] = to[i];
}
}
scanf("%d",&s);
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= s;++j)
scanf("%lf",rate[i] + j);
dfs(1);
printf("%.4f\n",f[1][s]);
}