Hellc

【题目描述】

给出一个有向无环的连通图，起点为 $1$ 终点为 $N$ ，边有边权。

从起点走向终点，到达每一个顶点时，如果有 $K$ 条离开该点的道路，可以选择任意一条道路离开该点，并且走向每条路的概率为 $\frac 1 K$ 。

求从起点 $1$ 到终点 $N$ 的路径长度的期望。

【题目链接】

BZOJ 3036 绿豆蛙的归宿

【解题思路】

期望 DP 入门题。

方法一：

直接 DP，设 $f[i]$ 表示从 $i$ 到终点的路径长度的期望。

我们可以根据全期望公式来转移（其中 $d_i$ 表示点 $i$ 的出度）：

$$ f[i] = \sum_{(i, j) \in E} \frac 1 {d_i} \times (f[j] + w(i, j)) $$

即考虑 $i$ 的所有出边，沿任一条边走过去的概率为 $\frac 1 d_i$，而其期望长度为 $f[j] + w(i, j)$。

由于图是 DAG，所以这个 DP 可以递推，按照拓扑序的逆序计算即可。

方法二：

根据期望的线性性质，路径长度的期望等于每条边的期望贡献之和，而每条边的期望贡献即为经过该边的期望次数乘上边权。

经过某边的期望次数不好计算，我们考虑计算经过某个点的期望次数，然后用其计算经过某边的期望次数。

设点 $i$ 的期望经过次数为 $f_i$ ，则对于边 $(u, v)$，经过其的期望次数为：

$$ f_u \times \frac 1 d_u $$

接下来我们考虑如何计算 $f_i$，考虑一个点的所有入边：

$$ f_i = \sum_{(j, i) \in E} f_j \times \frac 1 d_j $$

这是比较显然的。

考虑每个点可以转移到那儿也是可以的：

$$ f_j \leftarrow f_i \times \frac 1 d_i, (i, j) \in E $$

这样可以一边 DP 一边计算贡献，比较方便。

在实践中，方法二的应用更多，尽管在本题中还看不出其优势。

【AC代码】

方法一

#include <iostream>
#include <iomanip>
 
const int MAXN = 100000;
 
int n, m;
 
struct Node{
    struct Edge *edges;
    int inDeg, otDeg;
    double exLen;
 
    Node() : edges(NULL), exLen(0), inDeg(0), otDeg(0) {}
} nodes[MAXN];
 
struct Edge{
    Node *to;
    Edge *next;
    int w;
 
    Edge(Node *fr, Node *to, int w) : to(to), next(fr->edges), w(w) {}
};
 
inline void addEdge(Node *u, Node *v, int w){
    u->edges = new Edge(u, v, w);
    u->otDeg++, v->inDeg++;
}
 
Node* Q[MAXN];
inline void topo(Node *s){
    int l = 0, r = 0;
    Q[r++] = s;
    while(l != r){
        Node *v = Q[l++];
        for(Edge *e = v->edges; e; e = e->next){
            if(!--e->to->inDeg) Q[r++] = e->to;
        }
    }
}
 
inline double solve(){
    topo(nodes);
 
    (nodes + n - 1)->exLen = 0;
    for(int i = n - 2; i >= 0; i--){
        Node *v = nodes + i;
 
        v->exLen = 0;
        for(Edge *e = v->edges; e; e = e->next){
            v->exLen += (e->to->exLen + e->w) / v->otDeg;
        }
    }
 
    return nodes->exLen;
}
 
int main(){
    std::cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, w;
        std::cin >> u >> v >> w, u--, v--;
 
        addEdge(nodes + u, nodes + v, w);
    }
 
    std::cout.setf(std::ios::fixed);
    std::cout << std::setprecision(2) << solve() << std::endl;
 
    return 0;
}

方法二

#include <iostream>
#include <iomanip>
 
const int MAXN = 100000;
 
int n, m;
 
struct Node{
    struct Edge *edges;
    int inDeg, otDeg;
    double ex;
 
    Node() : edges(NULL), ex(0), inDeg(0), otDeg(0) {}
} nodes[MAXN];
 
struct Edge{
    Node *to;
    Edge *next;
    int w;
 
    Edge(Node *fr, Node *to, int w) : to(to), next(fr->edges), w(w) {}
};
 
inline void addEdge(Node *u, Node *v, int w){
    u->edges = new Edge(u, v, w);
    u->otDeg++, v->inDeg++;
}
 
Node* Q[MAXN];
inline void topo(Node *s){
    int l = 0, r = 0;
    Q[r++] = s;
    while(l != r){
        Node *v = Q[l++];
        for(Edge *e = v->edges; e; e = e->next){
            if(!--e->to->inDeg) Q[r++] = e->to;
        }
    }
}
 
inline double solve(){
    topo(nodes);
 
    double ans = 0;
 
    nodes->ex = 1; 
    for(int i = 0; i < n; i++){
        Node *v = Q[i];
 
        for(Edge *e = v->edges; e; e = e->next){
            e->to->ex += v->ex / v->otDeg;
            ans += v->ex * e->w / v->otDeg;
        }
    }
 
    return ans;
}
 
int main(){
    std::cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, w;
        std::cin >> u >> v >> w, u--, v--;
 
        addEdge(nodes + u, nodes + v, w);
    }
 
    std::cout.setf(std::ios::fixed);
    std::cout << std::setprecision(2) << solve() << std::endl;
 
    return 0;
}

就是这样咯~