HDU5036(bitset加速传递闭包+期望)

HDU5036 题解

题目链接

思路:

求出破坏or打开所有门所需要的期望炮弹数量，那么根据期望的线性性质，我们可以求出每一个门的期望值最后累加起来就行了。

我们最后的目标就是求对于一个门\(i\)，有多少门可以到达\(i\)，假设有\(s\)个门(包含\(i\))，那么\(E_i=1*\frac{1}{s}\)。

那么我们就需要知道如果打开一个门，还能打开什么其它的门，这有点类似于传递闭包，但这题\(n\)最高有1000，这里我们用\(bitset\)加速一下就好了。这里的floyd还是挺有意思的，可以仔细琢磨一下。

代码如下：

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <bitset>

using namespace std;

typedef long long ll;

const int N = 1005;

int T;

int n;

bitset <N> d[N];

int main() {

    cin >> T;

    for(int Case = 1; Case <= T; Case++) {

        scanf("%d", &n) ;

        for(int i = 1; i <= n; i++) d[i].reset() ;

        for(int i = 1, k; i <= n; i++) {

            scanf("%d", &k);

            d[i].set(i) ;

            for(int j = 1, x; j <= k; j++) {

                scanf("%d", &x) ;

                d[x].set(i) ;

            }

        }

        for(int i = 1; i <= n; i++)

            for(int j = 1; j <= n; j++)

                if(d[j].test(i)) d[j] |= d[i] ;

        double ans = 0;

        for(int i = 1; i <= n; i++) ans += 1.0 / d[i].count() ;

        printf("Case #%d: %.5f\n", Case, ans) ;

    }

    return 0;

}