Uva(11600)(Masud Rana )

链接：https://vjudge.net/problem/UVA-11600
思路：主要是状态的考虑，因为每两个点都有路，所以只用区分有没有怪兽即可，我们可以算从一个点开始走到全部两两连通的时候的概率，这时候我们需要用一个数来表示当前已经两两连通的点的集合，状态转移就是枚举不在集合中的点，dp[u][s] += DP(i,(s|(1<<i)) * num[i] / (n-have) ，表示选一个没在集合中的点的期望的总和，由于期望是概率的倒数，所以一开始我们计算的时候就可以入上倒过来计算，需要预处理一下原图，将各个已经连通块的数目统计出来即可。
代码：

#include<bits/stdc++.h>
using namespace std;

int t,n,m;
const int maxn = 105;
const int maxm = maxn*maxn;
map<int,double> dp[maxn];
vector<int> G[maxn];
int vis[maxn];
int num[maxn];
int _num;

int dfs(int u){
    vis[u] = 1;
   int ans = 1;
    for(int i=0;i<G[u].size();i++){
        if(!vis[G[u][i]])ans+=dfs(G[u][i]);
    }
    return ans;
}

double DP(int u,int s){
    if(dp[u].count(s))return dp[u][s];
    int have = 0,i;
    for(i=0;i<_num;i++){
        if(s&(1<<i))have+=num[i];
    }
    if(have==n)return dp[u][s] = 0;
    dp[u][s] = (n-1)*1.0/(n-have);
    for(int i=0;i<_num;i++){
        if(s&(1<<i))continue;
        dp[u][s] += DP(i,s|(1<<i))*num[i]/(n-have);
    }
    return dp[u][s];
}

int main(){
    scanf("%d",&t);
    int kase = 0;
    while(t--){
        memset(num,0,sizeof(num));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<=n;i++){
            G[i].clear();
        dp[i].clear();
        }
        _num = 0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
       for(int i=1;i<=n;i++){
           if(!vis[i]){
               num[_num++] = dfs(i);
           }
       }
       printf("Case %d %.6lf\n",++kase,DP(0,1));
    }
    return 0;
}