首页 > 代码库 > HDU5036 Explosion(期望&&bitset)

HDU5036 Explosion(期望&&bitset)

 

#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <algorithm>#include <cmath>#include <bitset>using namespace std;#define maxn 1005bitset<1100> b[maxn];int n;int main(){    int T;cin>>T;int ca=0;    while(T--){        scanf("%d",&n);        for(int i=1;i<=n;++i) b[i].reset();        for(int i=1;i<=n;++i){            int num;scanf("%d",&num);            b[i][i]=true;            while(num--){                int tmp;                scanf("%d",&tmp);                b[i][tmp]=true;            }        }        for(int i=1;i<=n;++i){            for(int j=1;j<=n;++j){                if(b[j][i]) b[j]|=b[i];            }        }        double ans=0;        for(int i=1;i<=n;++i){            int cnt=0;            for(int j=1;j<=n;++j){                if(b[j][i]) ++cnt;            }            ans+=1.0/cnt;        }        printf("Case #%d: %.5lf\n",++ca,ans);    }    return 0;}

 

HDU5036 Explosion(期望&&bitset)