这道题甚至不如 T2 难...放在 T3 真的合适吗...

题目链接

<h2>题目描述</h2>

一张无向带权图，需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中，有 $ p_i $ 的概率选择点 $ d_i $，有 $ 1-p_i $ 的概率选择点 $ c_i $ ，每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现在求出所有选择的路线方案中的最小期望值。

<h2>解题报告</h2>

看到期望了直接弃疗

这一题考的是期望的基本知识，所以大可不用弃疗。

感觉就是出题人为了强行增加难度套了个期望？

对于期望计算就是事件价值/代价 $*$ 概率，对其求和。

这样我们首先发现点非常的少，Floyd 处理最短路。

然后我们考虑动态规划。设 $ f[i][j][1/0] $ 表示考虑到第 $i$ 次选择，已经选择了 $j$ 次 $d$ 类节点，这一次是否选 $d$ 类节点的最小期望值。

显然转移方程如下：

设 $ dis[i][j] $ 表示 i 到 j 的最短路，$ c[i],d[i],p[i] $ 如题目所述。

dp转移代码如下（公式太长了写不开）

c++
fi[0] = std::min(fi-1[0]+map[c[i-1]][c[i]],fi-1[1] + p[i-1] map[d[i-1]][c[i]] + map[c[i-1]][c[i]] (1.0-p[i-1]));
fi[1] = std::min(fi-1[0] + map[c[i-1]][d[i]]p[i] + map[c[i-1]][c[i]](1-p[i]),fi-1[1] + map[c[i-1]][c[i]] (1-p[i-1])(1-p[i]) + map[c[i-1]][d[i]] (1-p[i-1])p[i] + map[d[i-1]][c[i]] p[i-1](1-p[i]) + map[d[i-1]][d[i]] p[i-1] p[i]);

这个方程的细节很多，还请读者自己体会。

其实就是加上所有的期望。

<h2>样例代码</h2>

#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>

const int MAXN = 2000 + 5;

double p[MAXN],mapMAXN,fMAXN[2];
int c[MAXN],d[MAXN];
int N,M,v,e;

inline void Read(){
    scanf("%d%d%d%d",&N,&M,&v,&e);
    for(int i = 1;i <= N;i++)
        scanf("%d",c + i);
    for(int i = 1;i <= N;i++)
        scanf("%d",d+i);
    for(int i = 1;i <= N;i++)
        scanf("%lf",p+i);
    for(int i = 1;i <= v;i++)
        for(int j = 1;j <= v;j++)
            mapi = (double)INT_MAX;
    for(int i = 1;i <= v;i++)
        mapi = 0;
    double w;
    for(int u,v,i = 1;i <= e;i++){
        scanf("%d%d%lf",&u,&v,&w);
        mapu = mapv = std::min(w,mapu);
    }
}

inline void Floyd(){
    for(int k = 1;k <= v;k++)
        for(int i = 1;i <= v;i++)
            for(int j = 1;j <= v;j++)
                mapi = std::min(mapi,mapi + mapk);
}

inline void dp(){
    for(int i = 1;i <= N;i++)
        for(int j = 0;j <= M;j++)
            fi[0] = fi[1] = (double)INT_MAX;
    f1[0] = f1[1] = 0.0;
    for(int i = 2;i <= N;i++){ //fi[k]->时刻 i，更换 j。
        for(int j = 0;j <= M;j++){
            fi[0] = std::min(fi-1[0]+map[c[i-1]][c[i]],fi-1[1] + p[i-1]  map[d[i-1]][c[i]] + map[c[i-1]][c[i]]  (1.0-p[i-1]));
            if(j){
                fi[1] = std::min(fi-1[0] + map[c[i-1]][d[i]]p[i] + map[c[i-1]][c[i]](1-p[i]),fi-1[1] + map[c[i-1]][c[i]]  (1-p[i-1])(1-p[i]) + map[c[i-1]][d[i]]  (1-p[i-1])p[i] + map[d[i-1]][c[i]]  p[i-1](1-p[i]) + map[d[i-1]][d[i]]  p[i-1]  p[i]);
            }
        }
    }
    double ans = (double)INT_MAX;
    for(int i = 0;i <= M;i++)
        ans = std::min(ans,std::min(fN[0],fN[1]));
    printf("%.2fn",ans);
}

int main(){
    Read();
    Floyd();
    dp();
    return 0;
}