一般的期望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)
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
const int INF = << ;
typedef __int64 LL;
/* */
const int N = + ;
std::vector<int> g[N];
std::map<int, double> dp[N];
int cnt[N];
int p, n;
bool vis[N];
int dfs(int u)
{
vis[u] = true;
int ret = ;
for (int i = ;i < g[u].size();++i)
{
int v = g[u][i];
if (vis[v]) continue;
ret += dfs(v);
}
return ret;
} double DP(int u, int s)
{
int have = ;
if (dp[u].count(s)) return dp[u][s];
for (int i = ;i < n;++i)
if (s&( << i))
have += cnt[i];
if (have == n) return ;//dp[][n] 的期望是0
dp[u][s] = (n - )*1.0 / (n - have);
for (int i = ;i < p;++i)
{
if (s&( << i)) continue;
dp[u][s] += DP(i, s|( << i)) * cnt[i] / (n - have);
}
return dp[u][s];
}
int main()
{
int t, m;
scanf("%d", &t);
for (int k = ;k <= t;++k)
{
scanf("%d%d", &n, &m);
p = ;
for (int i = ;i <= n;++i)
{
g[i].clear();
vis[i] = ;
}
int u, v;
for (int i = ;i < m;++i)
{
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = ;i <= n;++i)
if (!vis[i])
{
dp[p].clear();
cnt[p++] = dfs(i);
} printf("Case %d: %.6lf\n",k, DP(, ));
}
return ;
}