Uva 11600 期望DP

题意：n个城市，相互可达（有n(n-1)/2条边），其中有一些道路上面有妖怪，现在，从1号城市出发，随机挑取一个城市走去，这个道路上的妖怪就会被消灭，求：

在平均情况下，需要走多少步，使得任意两个城市之间，可以不经过妖怪而相互可达；

(n<=30)

分析：

1、根据题意可知，我们要将每一个可以不经过妖怪的一个个连通分量找出来；

2、然后从一个连通分量走到另一个连通分量，这时肯定进过妖怪；

3、一个一个连通分量，完成了哪几个连通分量，需要保存，这时，就用集合的方式保存；

4、从一个连通分量，走到另一个连通分量，其概率 n-con/(n-1) ，那么平均要走 n-1 / (n-con)　次；

5、状态转移，下一个状态s|(i<<n)，和走向这个状态的概率；

#include <bits/stdc++.h>

using namespace std;

int n,m;

vector<int> g[];

int cnt;

int num[];

bool vis[];

int dfs(int u) {

    int count = ;

    vis[u] = ;

    for(int i=;i<g[u].size();i++) {

        int v = g[u][i];

        if(!vis[v])

            count+=dfs(v);

    }

    return count;

}

map<int,double> f;

double dp(int s) {

    if(f[s]>1e-)

        return f[s];

    int con = ;

    for(int i=;i<cnt;i++)

        if(s&(<<i))

            con+=num[i];

    if(con==n)

        return f[s] = ;

    f[s] = (n-)*1.0/(n-con);

    for(int i=;i<cnt;i++) {

        if(!(s&(<<i)))

            f[s] +=dp(s|(<<i))*num[i]*1.0/(n-con);

    }

    return f[s];

}

int main()

{

    int t;

    scanf("%d",&t);

    int kase = ;

    while(t--) {

        scanf("%d%d",&n,&m);

        f.clear();

        for(int i=;i<=n;i++)

            g[i].clear();

        cnt = ;

        memset(vis,,sizeof(vis));

        memset(num,,sizeof(num));

        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])

                num[cnt++] = dfs(i);

        }

        printf("Case %d: %lf\n",++kase,dp());

    }

    return ;

}