HDU 5036 Explosion (传递闭包+bitset优化)

<题目链接>

题目大意:

一个人要打开或者用炸弹砸开所有的门,每个门后面有一些钥匙,一个钥匙对应一个门,告诉每个门里面有哪些门的钥匙。如果要打开所有的门,问需要用的炸弹数量为多少。 解题分析:
因为许多门和他们之后的钥匙可能形成闭包的关系,所以,对于所有的闭包而言,只需要炸毁其中的一个门,就可以用其后面的钥匙打开闭包中至少一扇另外的门,一次类推。所以,假设闭包中包含$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

 

上一篇:JSOI2010 连通数


下一篇:bitset基本操作