hdu5306 Explosion

题目链接

题意

有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;

}