题意
有n个房间，每个房间里面有若干把钥匙，每把钥匙可以打开对应的一扇门。如果手中没有钥匙，就要随机轰炸一个房间来打开这个房间。如果有钥匙，就要去打开这些房间。问期望轰炸次数是多少。
思路
根据期望的线性性质，总期望轰炸次数就是每个房间被轰炸的概率\(\times\) 1。
所以就考虑每个房间被轰炸的概率。
先理解一下题意，也就是说只要打开了一扇门就可以打开若干扇门。所以可以从每个房间向他房间中钥匙所对应的房间连边。
每个房间被轰炸当且仅当所有可以到达他的房间都没有被轰炸。
所以把上面所说的边放过了。跑一边传递闭包。第i个点被轰炸的概率就是\(1/anc(i)\)，\(anc(x)\)表示在传递闭包中x所能到达的点的个数。
求传递闭包可以用\(floyd\)，再加上\(bitset\)的优化
所以最终答案就是$$\sum_{i=1}^n\frac{1}{anc_i}$$
代码
/*
* @Author: wxyww
* @Date: 2019-01-23 15:39:31
* @Last Modified time: 2019-01-23 16:03:40
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 1010;
bitset<N>f[N];
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void solve(int x) {
int n = read();
for(int i = 1;i <= n;++i) {
int k = read();
f[i].set(i);
for(int j = 1;j <= k;++j) {
int x = read();
f[x].set(i);
}
}
for(int k = 1;k <= n;++k)
for(int i = 1;i <= n;++i)
if(f[i][k]) f[i] |= f[k];
double ans = 0;
for(int i = 1;i <= n;++i) {
ans += (double)1 / f[i].count();
f[i].reset();
}
printf("Case #%d: %.5lf\n",x,ans);
}
int main() {
int T = read();
for(int i = 1;i <= T;++i) {
// MEM();
solve(i);
}
return 0;
}