AGC049A 题解

弱化版：CF280C Game on Tree（有向图的限制变成一棵根节点为 1 的外向树）

弱化版解法：

根据期望线性性，\(Ans=\sum_{i=1}^nE(p_i)\)。

其中 \(p_i\) 是 \(i\) 被选到的概率。

因为对于 \(i\) 和 \(i\) 的祖先节点，某个点在这些店里是第一个备选的概率相同。所以 \(p_i=\dfrac{1}{dep_i}\)。

所以答案就是 \(\sum_{i=1}^n\dfrac{1}{dep_i}\)。

回到这道题，根据上面结论，\(p_i=\dfrac{1}{可以到达i的点的个数}\)。

直接 bitset 传递闭包。

复杂度 \(O\left(\dfrac{n^3}{w}\right)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 105;
int n;

long double ans;
vector<int> e[N];
int deg[N];
bitset<N> g[N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        string s; cin >> s;
        g[i][i] = 1;
        for(int j = 1; j <= n; j ++)
            if(s[j - 1] == '1')
                g[j][i] = 1;
    }
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
        if(g[j][i]) g[j] |= g[i];
    for(int i = 1; i <= n; i ++)
        ans += 1.L / g[i].count();
    printf("%.20Lf", ans);

    return 0;
}