JZOJ 4215 与机关的决战

首先跑一遍单源最短路，只保留最短路上的边，发现是一棵树。
于是显然的树形 DP 套路。

设 fi,j 表示 FB 从 i 出发，以 i 为根的子树总共有 j 个 Labmem，抓捕到 FB 的最大概率。
转移比较显然，对于每个 i,j，枚举 i 上放的 Labmem 个数，并对儿子构成的子树做背包。
注意，我们不需要对于每个 i,j 都做背包，因为背包跟 j 没有关，所以对于 i 做即可。

复杂度 O(n⋅s2)。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
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]);
}