BZOJ1415（期望dp）

解法：

首先bfs预处理go数组：可可在j点时聪聪在点i是怎样贪心走的，这是为了之后O（1）获取转移线路。

然后dfs记忆化一下f[i][j]，代表从i到j的期望，对于每层：将所有情况的期望值相加。边界值是聪聪与可可在同一个点期望为0、聪聪一步或两步可到可可处期望为1。

 1 const int maxn = 1005;
 2 int n, m, st, ed;
 3 vector<int> dd[maxn];
 4 int go[maxn][maxn];
 5 db f[maxn][maxn];
 6 
 7 void bfs() {
 8     for (int i = 1; i <= n; i++)
 9         sort(dd[i].begin(), dd[i].end());
10     for (int i = 1; i <= n; i++) {
11         queue<P> Q;
12         bool vis[n + 1];
13         memset(vis, false, sizeof vis);
14         vis[i] = true;
15         for (int t = 0; t < dd[i].size(); t++) {
16             int j = dd[i][t];
17             Q.push(P(j, j));
18             vis[j] = true;
19             go[i][j] = j;
20         }
21         while (!Q.empty()) {
22             P x = Q.front(); Q.pop();
23             for (int t = 0; t < dd[x.first].size(); t++) {
24                 int j = dd[x.first][t];
25                 if (!vis[j]) {
26                     vis[j] = true;
27                     go[i][j] = x.second;
28                     Q.push(P(j, x.second));
29                 }
30             }
31         }
32     }
33 }
34 
35 db dfs(int i, int j) {
36     if (i == j)    return f[i][j] = 0;
37     if (go[i][j] == j || go[go[i][j]][j] == j)    return f[i][j] = 1;
38     if (f[i][j] == 0) {
39         db p = dd[j].size() + 1;
40         int nx = go[go[i][j]][j];
41         for (int k = 0; k < dd[j].size(); k++) {
42             f[i][j] += dfs(nx, dd[j][k]);
43         }
44         f[i][j] += dfs(nx, j);
45         f[i][j] = f[i][j] / p + 1;
46     }
47     return f[i][j];
48 }
49 
50 int main() {
51     read(n), read(m), read(st), read(ed);
52     for (int i = 1; i <= m; i++) {
53         int u, v;
54         read(u), read(v);
55         dd[u].push_back(v);
56         dd[v].push_back(u);
57     }
58     bfs();
59     printf("%.3lf
", dfs(st, ed));
60     return 0;
61 }