[SHOI2011] 扫雷机器人 题解

前言

显然，一个炸弹可以引爆另一个，而另一个炸弹却不一定能引爆这一个。

考虑假设炸弹一能引爆炸弹二，则建一条一到二的有向边。

推导过程

期望，就是平均值，也就是所有情况的权值总和除以情况总数的值。

可是，情况总数足足有 $n!$ 种，显然会超时到没边。

当你走投无路的时候，可以尝试化简式子。

令全部的引爆次数为 $cnt$，期望为 $ans$，可以写出以下式子：

$$ans=\frac{cnt}{n!}$$

考虑 $cnt$ 该如何计算。

考虑每个炸弹对于 $cnt$ 的贡献。

显然这个炸弹被手动引爆一次，那么 $cnt$ 就会多 $1$。

考虑什么时候这个炸弹能够被手动引爆。

显然，每个炸弹都有若干个炸弹可以将其引爆，所以为了被手动引爆，这个炸弹的引爆时间必须在能引爆它的炸弹的前边。

令对于第 $i$ 个炸弹，有 $k_i$ 个炸弹可以将它引爆，为了方便计算，此处的 $k_i$ 包含第 $i$ 个炸弹本身。

显然第 $i$ 个炸弹被手动引爆的概率 $s_i$ 如下：
$$s_i=\frac{1}{k_i!}$$
那么第 $i$ 个炸弹能够被手动引爆的次数 $t_i$ 为：
$$t_i=\frac{1}{k_i!}\cdot n!$$
将这些式子代入计算期望的式子，得：
$$ans=\frac{{\sum }_{i=1}^n\frac{1}{k_i!}\cdot n!}{n!}$$
提取公因式，得：
$$ans=\frac{n!\cdot {\sum }_{i=1}^n\frac{1}{k_i!}}{n!}$$
化简，得：
$$ans=\sum _{i=1}^n\frac{1}{k_i!}$$
这个式子就能计算了，但 $k_i$ 该如何计算？

一下子就想到了拓扑排序。

可是可能存在环。

考虑使用 Tarjan 算法进行 缩点，再进行拓扑排序。

参考代码

#include<bits/stdc++.h>
using namespace std;
struct bomb{
    int x;
    int d;
}a[4010];
int n;
bitset<4010>k[4010];
vector<int>e[4010];
set<int>b[4010];
int low[4010];
int dfn[4010];
int vis[4010];
int d[4010];
stack<int>s;
int idx;
vector<vector<int>>ans;
int id[4010];
void Tarjan(int x){
    s.push(x);
    low[x]=dfn[x]=++idx;
    vis[x]=1;
    for(int i:e[x]){
        if(!dfn[i]){
            Tarjan(i);
            low[x]=min(low[x],low[i]);
        }else if(vis[i]){
            low[x]=min(low[x],dfn[i]);
        }
    }
    if(low[x]==dfn[x]){
        vector<int>q;
        while(s.top()!=x){
            auto h=s.top();
            s.pop();
            vis[h]=0;
            q.push_back(h);
            id[h]=ans.size();
        }
        s.pop();
        vis[x]=0;
        q.push_back(x);
        id[x]=ans.size();
        ans.push_back(q);
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].d;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i^j && a[i].x-a[i].d<=a[j].x && a[i].x+a[i].d>=a[j].x){
                e[i].push_back(j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            Tarjan(i);
        }
    }
    for(int i=0;i<ans.size();i++){
        for(int j:ans[i]){
            k[i][j]=1;
            for(int k:e[j]){
                if(i==id[k])continue;
                b[i].emplace(id[k]);
            }
        }
    }
    for(int i=0;i<ans.size();i++){
        for(int j:b[i]){
            d[j]++;
        }
    }
    queue<int>q;
    for(int i=0;i<ans.size();i++){
        if(!d[i])q.push(i);
    }
    while(!q.empty()){
        auto h=q.front();
        q.pop();
        for(int i:b[h]){
            k[i]|=k[h];
            d[i]--;
            if(!d[i])q.push(i);
        }
    }
    long double e=0.000000;
    for(int i=0;i<ans.size();i++){
        e+=(1.000000)/(k[i].count()*1.000000)*ans[i].size();
    }
    cout<<fixed<<setprecision(4)<<e;
    return 0;
}

如有错误，还请指出。

注. 我的洛谷账号即为 lonys，本篇文章同步在洛谷专栏发布。