一般的期望dp是， dp[i] = dp[j] * p[j] + 1; 即走到下一步需要1的时间，然后加上 下一步走到目标的期望*这一步走到下一步的概率
这一题，我们将联通分块缩为一个点，因为联通块都是安全的
dp[u][s] 为当前在u，走过的联通块为s的期望天数
那么走到剩下没有走过的连通块的概率是 (n-have)/(n-1), 那么平均需要的时间是 (n-1)/(n-have),
走到下一个没有走过的连通块的概率为cnt[i] / (n-have)
所以dp[u][s] = (n-1)/(n-have) + dp[i][s|1<<i] * cnt[i]/(n-have)
1 #pragma warning(disable:4996) 2 #pragma comment(linker, "/STACK:1024000000,1024000000") 3 #include <stdio.h> 4 #include <string.h> 5 #include <time.h> 6 #include <math.h> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <stack> 11 #include <vector> 12 #include <bitset> 13 #include <algorithm> 14 #include <iostream> 15 #include <string> 16 #include <functional> 17 const int INF = 1 << 30; 18 typedef __int64 LL; 19 /* 20 21 */ 22 const int N = 30 + 10; 23 std::vector<int> g[N]; 24 std::map<int, double> dp[N]; 25 int cnt[N]; 26 int p, n; 27 bool vis[N]; 28 int dfs(int u) 29 { 30 vis[u] = true; 31 int ret = 1; 32 for (int i = 0;i < g[u].size();++i) 33 { 34 int v = g[u][i]; 35 if (vis[v]) continue; 36 ret += dfs(v); 37 } 38 return ret; 39 } 40 41 double DP(int u, int s) 42 { 43 int have = 0; 44 if (dp[u].count(s)) return dp[u][s]; 45 for (int i = 0;i < n;++i) 46 if (s&(1 << i)) 47 have += cnt[i]; 48 if (have == n) return 0;//dp[][n] 的期望是0 49 dp[u][s] = (n - 1)*1.0 / (n - have); 50 for (int i = 0;i < p;++i) 51 { 52 if (s&(1 << i)) continue; 53 dp[u][s] += DP(i, s|(1 << i)) * cnt[i] / (n - have); 54 } 55 return dp[u][s]; 56 } 57 int main() 58 { 59 int t, m; 60 scanf("%d", &t); 61 for (int k = 1;k <= t;++k) 62 { 63 scanf("%d%d", &n, &m); 64 p = 0; 65 for (int i = 1;i <= n;++i) 66 { 67 g[i].clear(); 68 vis[i] = 0; 69 } 70 int u, v; 71 for (int i = 0;i < m;++i) 72 { 73 scanf("%d%d", &u, &v); 74 g[u].push_back(v); 75 g[v].push_back(u); 76 } 77 for (int i = 1;i <= n;++i) 78 if (!vis[i]) 79 { 80 dp[p].clear(); 81 cnt[p++] = dfs(i); 82 } 83 84 printf("Case %d: %.6lf ",k, DP(0, 1)); 85 } 86 return 0; 87 }