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