题解 P4206 【[NOI2005]聪聪与可可 】

经典的期望题，用记忆化搜索解决 ``` #include<cstdio> #include<cstring> #include<queue> using namespace std; int degree[1005], x[1005][1005], dis[1005][1005]; double f[1005][1005]; //degree记录每个点的度，x[i][j]代表聪聪在i，可可在j时聪聪的下一步 //dis[i][j]代表i、j距离 struct Edge { int to, next; }edge[2005]; int first[1005], size_of_edge; void Add_edge(int from, int to) { edge[++size_of_edge] = (Edge) { to, first[from] }; first[from] = size_of_edge; edge[++size_of_edge] = (Edge) { from, first[to] }; first[to] = size_of_edge; ++degree[from], ++degree[to]; } double dp(int i, int j) { if (f[i][j] != -1.0)//已经算过 return f[i][j]; if (i == j)//已经抓到 return f[i][j] = 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 = first[j]; k; k = edge[k].next)//枚举下一步 f[i][j] += dp(x[x[i][j]][j], edge[k].to); f[i][j] = (f[i][j] + dp(x[x[i][j]][j], j)) / (double)(degree[j] + 1) + 1; return f[i][j]; } int main() { int n, e, c, m, from, to; scanf("%d%d%d%d", &n, &e, &c, &m); while (e--) { scanf("%d%d", &from, &to); Add_edge(from, to); } //链式前向星存图 for (int i = 0; i < n + 1; ++i) for (int j = 0; j < n + 1; ++j) f[i][j] = -1.0; //初始化答案数组 memset(dis, -1, sizeof(dis)); for (int i = 1; i <= n; ++i) { queue<int> que; que.push(i); dis[i][i] = 0; while (!que.empty()) { from = que.front(); que.pop(); for (int j = first[from]; j; j = edge[j].next) { to = edge[j].to; if (dis[i][to] == -1) { dis[i][to] = dis[i][from] + 1; que.push(to); } } } } //BFS遍历求出图中所有点对的距离 memset(x, 0x7f, sizeof x); //因为聪聪会选择编号小的点，因此把x初始化为maxint for (int from = 1; from <= n; ++from) { for (int k = first[from]; k; k = edge[k].next) { for (int j = 1; j <= n; ++j) { if (dis[from][j] == dis[edge[k].to][j] + 1 && x[from][j]>edge[k].to) { x[from][j] = edge[k].to; } } } } //预处理聪聪的下一步 printf("%.3f\n", dp(c, m)); return 0; } ```