传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1415
noip2016 D1T3，多么痛的领悟。。。看来要恶补一下与期望相关的东西了。
这是一道经典的求期望的题，尽管我的代码里把那个记忆化搜索那个叫做dp，但事实上这不是动态规划，只是递推。
先预处理出x[i][j]，表示聪聪在i，可可在j时，下一步聪聪到达的顶点标号，f[i][j]是那张记忆化搜索的表，表示聪聪在i，可可在j时，期望所需的时间，out[i]表示i点的出度（其实就是度啦，无向图没什么入度出度的）。显然，下一个单位时间聪聪的位置是x[x[i][j]][j]，而可可是在所有与j相邻的节点或者j自己中随机挑一个到达，每个的概率都是1 / (out[j] + 1)，所以有
f[i][j] = ( sigma( f[x[x[i][j]][j]][k] ) + f[x[x[i][j]][j]][j] ) / (out[j] + 1) + 1，其中k表示每个与j相邻的节点。
然后写一个记忆化搜索就完事咯~
#include#include const int maxn = 1005, maxe = 1005;int n, e, ini_neko, ini_mouse, t1, t2;int head[maxn], to[maxe << 1], next[maxe << 1], lb, out[maxn];int que[maxn], head_, tail, h, x[maxn][maxn], d[maxn][maxn];double f[maxn][maxn];inline void ist(int aa, int ss) { to[lb] = ss; next[lb] = head[aa]; head[aa] = lb; ++out[aa]; ++lb;}double dp(int i, int j) { if (f[i][j] != -1.0) { return f[i][j]; } if (i == j) { return f[i][j] = 0.0; } if (x[i][j] == j) { return f[i][j] = 1.0; } if (x[x[i][j]][j] == j) { return f[i][j] = 1.0; } f[i][j] = 0.0; for (int k = head[j]; k != -1; k = next[k]) { f[i][j] += dp(x[x[i][j]][j], to[k]); } f[i][j] = (f[i][j] + dp(x[x[i][j]][j], j)) / (double)(out[j] + 1) + 1; return f[i][j];}int main(void) { //freopen("in.txt", "r", stdin); memset(head, -1, sizeof head); memset(next, -1, sizeof next); for (int i = 0; i < maxn; ++i) { for (int j = 0; j < maxn; ++j) { f[i][j] = -1.0; } } scanf("%d%d", &n, &e); scanf("%d%d", &ini_neko, &ini_mouse); while (e--) { scanf("%d%d", &t1, &t2); ist(t1, t2); ist(t2, t1); } memset(d, -1, sizeof d); for (int i = 1; i <= n; ++i) { memset(que, 0, sizeof que); head_ = tail = 0; que[tail++] = i; d[i][i] = 0; while (head_ != tail) { h = que[head_++]; for (int j = head[h]; j != -1; j = next[j]) { if (d[i][to[j]] == -1) { d[i][to[j]] = d[i][h] + 1; que[tail++] = to[j]; } } } } memset(x, 0x3c, sizeof x); for (int i = 1; i <= n; ++i) { for (int k = head[i]; k != -1; k = next[k]) { for (int j = 1; j <= n; ++j) { if (d[i][j] == d[to[k]][j] + 1 && x[i][j] > to[k]) { x[i][j] = to[k]; } } } } printf("%.3f\n", dp(ini_neko, ini_mouse)); return 0;}