题解 | #Fork in the Road#

【Fork in the Road】

定义 $d p (i)$ 为从房间 $i$ 到结束的期望。

先不考虑删边的情况，状态转移：

\begin{cases} dp(u)=\sum_{u\rightarrow v} \frac{1}{Graph[u].size}\cdot(dp(v)+1), & u\neq n \\ \\ dp(u)=0, & u= n \end{cases}

因为 $n\le 600$ ，所以可以直接枚举在房间 $i$ 后删除一条边，使得期望最小（贪心）。

枚举得到的所有 $d p (1)$ 的最小值就是答案，可以在 $O (n^{2})$ 内完成。

#include <bits/stdc++.h>
using namespace std;
const int N = 600 + 10;

vector<int> G[N];
int n, m;
double dp[N];

void solve(int k) {
    memset(dp, 0, sizeof dp);
    for(int i = n - 1; i >= 1; i--) {
        if(i == k && G[i].size() > 1) {
            double tmp = 0;
            for(int v : G[i]) {
                tmp = max(tmp, dp[v]);
                dp[i] += dp[v];
            }
            dp[i] -= tmp;
            dp[i] = dp[i] / (G[i].size() - 1) + 1;
        } else {
            for(int v : G[i]) dp[i] += dp[v];
            dp[i] = dp[i] / G[i].size() + 1;
        }
    }
}

int main() {
    cin >> n >> m;
    while(m--) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    double res = n;
    for(int i = 1; i < n; i++) {
        solve(i); // 枚举删边
        res = min(res, dp[1]);
    }
    printf("%.10lf", res);
    
    return 0;
}