概率期望+闭包+bitset优化——hdu5036

我们首先得到：

　　    暴力打开这个箱子，能够开那些箱子。这个可以用bitset来进行状态压缩。

           用闭包传递来解决这一步

　　    然后，对于每个箱子，我们考虑有多少种方法，使：暴力打开某些箱子，同时能打开这个箱子。

　　　暴力开这个箱子的期望就是方案数的倒数。然后我们对开每个箱子的期望求和就是最终的打开所有箱子暴力开箱子的数目的期望。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
bitset<1005>e[maxn];
int n,m;

void floyd(){
    for(int i=1;i<=n;i++)//枚举中介点 
        for(int j=1;j<=n;j++)
            if(e[j][i]==1)
                e[j]|=e[i];
}

int main(){
    int t;cin>>t;
    for(int tt=1;tt<=t;tt++){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)e[i].reset();
        
        for(int i=1;i<=n;i++){
            int k,x;scanf("%d",&k);
            while(k--){
                scanf("%d",&x);
                e[i][x]=1;
            }
            e[i][i]=1;
        }
        
        floyd();
        
        double ans=0;
        for(int i=1;i<=n;i++){
            double tot=0;
            for(int j=1;j<=n;j++)
                if(e[j][i]==1)tot+=1;
            ans+=1.0/tot;
        }
        printf("Case #%d: %.5lf
",tt,ans);
    }
}