http://acm.hdu.edu.cn/showproblem.php?pid=5036

n个房间每个房间里面有一把或多把钥匙可以打开其他的门。如果手上没有钥匙可以选择等概率随机选择一个门炸开，求用炸弹数的期望。

O(N^3)的复杂度过不了

单独考虑一个房间，如果有k个房间被炸开都会导致这个房间被打开。那么炸一次这个房间被打开的概率即为kn。也就意味着为了把这个房间打开的期望炸的次数为nk。

bitset第一次见..

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <bitset>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

const int INF = ( 1 << 30 );

int n;

bitset <1005> g[1005];

int cnt[1005];

int main()

{

    int _,cas = 1,k,x;

    RD(_);

    while(_--){

        printf("Case #%d: ",cas++);

        RD(n);

        clr0(cnt);

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

            g[i].reset();

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

            g[i][i] = 1;

            RD(k);

            while(k--){

                RD(x);

                g[x][i] = 1;

            }

        }

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

            for(int j = 1;j <= n;++j){

                if(g[j][i]) g[j] |= g[i];

            }

        }

        double ans = 0.0;

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

            for(int j = 1;j <= n;++j){

                if(g[i][j]) cnt[i]++;

            }

            ans += 1.0/(double)cnt[i];

        }

        printf("%.5lf\n",ans);

    }

    return 0 ;

}