期望dp

将有怪物的边视作断边,经过一条边则将边的两端连通

那么求的是任意两点彼此连通的期望天数

也就是从1开始可以到达任意一点

由于题目开始就连了一些边，所以将各个连通块视作点，并记录连通块的大小

为了方便，将1所在的连通块编号为1

记  f[s] 表示当前可到达的连通块集合为 s, 期望还需多少天可以覆盖全集

讨论下一个前往的连通块是否在集合内得到转移方程：

// i 为下一个前往的连通块编号, tot表示当前集合点数, s[i]表示编号为 i 的连通块大小

f[s] = (f[s]+1)*(tot-1)*(n-1) + (f[s|(1<<i-1)]+1)*s[i]/(n-1)

将 f[s]移到左边就可以算出 f[s]

注意特判n==1的情况，边界条件:当tot == n是答案为0

题目数据不强，可以用记忆化搜索通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 35;
 5 
 6 int T, n, m, kase, e[N][N], siz[N], cnt;
 7 bool vis[N];
 8 
 9 map<int, double> f;
10 
11 double dp(int s) {
12     if(f[s] > 0) return f[s];
13     int tot = 0;
14     for(int i = 0; i < cnt; i++)
15         if(s&(1<<i)) tot += siz[i + 1];
16     if(tot == n) return 0;
17     f[s] = 1.0*(tot - 1)/(n - 1);
18     for(int i = 1; i <= cnt; i++) 
19         if(!(s&(1<<(i - 1)))) 
20             f[s] += (dp(s|(1<<(i - 1))) + 1)*1.0*siz[i]/(n - 1);
21     f[s] = f[s]*1.0*(n - 1)/(n - tot);
22     return f[s];
23 }
24 
25 int dfs(int u) {
26     int res = 1;
27     vis[u] = 1;
28     for(int v = 1; v <= n; v++)
29         if(!vis[v] && e[v][u]) res += dfs(v);
30     return res; 
31 }
32 
33 int main() {
34     scanf("%d", &T);
35     while(T--) {
36         printf("Case %d: ", ++kase);
37         scanf("%d%d", &n, &m);
38         memset(e, 0, sizeof(e));
39         memset(vis, 0, sizeof(vis));
40         for(int u, v, i = 1; i <= m; i++) {
41             scanf("%d%d", &u, &v);
42             e[u][v] = e[v][u] = 1;
43         }
44         cnt = 0;
45         f.clear();
46         for(int i = 1; i <= n; i++)
47             if(!vis[i]) siz[++cnt] = dfs(i);
48         printf("%.7f\n", dp(1));
49     }
50 }

View Code