<题目链接>
题目大意：
一个人要打开或者用炸弹砸开所有的门，每个门后面有一些钥匙，一个钥匙对应一个门，告诉每个门里面有哪些门的钥匙。如果要打开所有的门，问需要用的炸弹数量为多少。
解题分析：
因为许多门和他们之后的钥匙可能形成闭包的关系，所以，对于所有的闭包而言，只需要炸毁其中的一个门，就可以用其后面的钥匙打开闭包中至少一扇另外的门，一次类推。所以，假设闭包中包含$num$扇门，用炸弹打开闭包中任意一扇门的概率就为：$1/num$(因为炸毁每个闭包的概率为1，即每个闭包必然需要一枚炸弹)。所有点的概率相加，得到的最终答案就是所需炸弹的数量。但是，由于本题的$n$给到了$10^3$，单纯的Floyd复杂度为$O(n^3)$，所以这里用到了bitset来优化常数。
因为许多门和他们之后的钥匙可能形成闭包的关系，所以，对于所有的闭包而言，只需要炸毁其中的一个门，就可以用其后面的钥匙打开闭包中至少一扇另外的门，一次类推。所以，假设闭包中包含$num$扇门，用炸弹打开闭包中任意一扇门的概率就为：$1/num$(因为炸毁每个闭包的概率为1，即每个闭包必然需要一枚炸弹)。所有点的概率相加，得到的最终答案就是所需炸弹的数量。但是，由于本题的$n$给到了$10^3$，单纯的Floyd复杂度为$O(n^3)$，所以这里用到了bitset来优化常数。
#include <bits/stdc++.h>
using namespace std;
const int N=;
bitset<N> b[N];
int n,ncase=;
double ans;
void Floyd(){ //Floyd传递闭包
ans=0.0;
for(int j=; j<n; j++)//对于每个房间j，枚举i,若i可以到达j，则i可以到达j可以到达的所有房间，即传递闭包。
for(int i=; i<n; i++)
if(b[i][j])b[i]|=b[j];
for(int j=; j<n; j++){ //得到每个以j为起点的闭包的节点数量
int cnt=;
for(int i=; i<n; i++)
if(b[i][j])cnt++;//对于j,看有多少个i可以直接或间接到达，最终该房间使用炸弹的期望为1.0/cnt,也就是平均要使用1.0/cnt个才能到达i;
ans=ans+(1.0/cnt);
}
printf("Case #%d: %.5lf\n",++ncase,ans);
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=; i<n; i++){
b[i].reset();
b[i][i]=;//一定可以到达自己所在房间。
}
for(int i=; i<n; i++){
int num;scanf("%d",&num);
for(int j=; j<num; j++){
int to;scanf("%d",&to);
b[i][to-]=;//从房间i可以到达的房间。
}
}
Floyd();
}
}
2019-03-06