[SHOI2011] 扫雷机器人 题解前言显然一个炸弹可以引爆另一个而另一个炸弹却不一定能引爆这一个。考虑假设炸弹一能引爆炸弹二则建一条一到二的有向边。推导过程期望就是平均值也就是所有情况的权值总和除以情况总数的值。可是情况总数足足有n ! n!n!种显然会超时到没边。当你走投无路的时候可以尝试化简式子。令全部的引爆次数为c n t cntcnt期望为a n s ansans可以写出以下式子a n s c n t n ! ans\frac{cnt}{n!}ansn!cnt​考虑c n t cntcnt该如何计算。考虑每个炸弹对于c n t cntcnt的贡献。显然这个炸弹被手动引爆一次那么c n t cntcnt就会多1 11。考虑什么时候这个炸弹能够被手动引爆。显然每个炸弹都有若干个炸弹可以将其引爆所以为了被手动引爆这个炸弹的引爆时间必须在能引爆它的炸弹的前边。令对于第i ii个炸弹有k i k_iki​个炸弹可以将它引爆为了方便计算此处的k i k_iki​包含第i ii个炸弹本身。显然第i ii个炸弹被手动引爆的概率s i s_isi​如下s i 1 k i ! s_i\frac{1}{k_i!}si​ki​!1​那么第i ii个炸弹能够被手动引爆的次数t i t_iti​为t i 1 k i ! ⋅ n ! t_i\frac{1}{k_i!}\cdot n!ti​ki​!1​⋅n!将这些式子代入计算期望的式子得a n s ∑ i 1 n 1 k i ! ⋅ n ! n ! ans\frac{\sum_{i1}^n\frac{1}{k_i!}\cdot n!}{n!}ansn!∑i1n​ki​!1​⋅n!​提取公因式得a n s n ! ⋅ ∑ i 1 n 1 k i ! n ! ans\frac{n!\cdot \sum_{i1}^n\frac{1}{k_i!}}{n!}ansn!n!⋅∑i1n​ki​!1​​化简得a n s ∑ i 1 n 1 k i ! ans\sum_{i1}^n\frac{1}{k_i!}ansi1∑n​ki​!1​这个式子就能计算了但k i k_iki​该如何计算一下子就想到了拓扑排序。可是可能存在环。考虑使用 Tarjan 算法进行 缩点再进行拓扑排序。参考代码#includebits/stdc.husingnamespacestd;structbomb{intx;intd;}a[4010];intn;bitset4010k[4010];vectorinte[4010];setintb[4010];intlow[4010];intdfn[4010];intvis[4010];intd[4010];stackints;intidx;vectorvectorintans;intid[4010];voidTarjan(intx){s.push(x);low[x]dfn[x]idx;vis[x]1;for(inti:e[x]){if(!dfn[i]){Tarjan(i);low[x]min(low[x],low[i]);}elseif(vis[i]){low[x]min(low[x],dfn[i]);}}if(low[x]dfn[x]){vectorintq;while(s.top()!x){autohs.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);}}intmain(){cin.tie(0)-sync_with_stdio(false);cinn;for(inti1;in;i){cina[i].xa[i].d;}for(inti1;in;i){for(intj1;jn;j){if(i^ja[i].x-a[i].da[j].xa[i].xa[i].da[j].x){e[i].push_back(j);}}}for(inti1;in;i){if(!dfn[i]){Tarjan(i);}}for(inti0;ians.size();i){for(intj:ans[i]){k[i][j]1;for(intk:e[j]){if(iid[k])continue;b[i].emplace(id[k]);}}}for(inti0;ians.size();i){for(intj:b[i]){d[j];}}queueintq;for(inti0;ians.size();i){if(!d[i])q.push(i);}while(!q.empty()){autohq.front();q.pop();for(inti:b[h]){k[i]|k[h];d[i]--;if(!d[i])q.push(i);}}longdoublee0.000000;for(inti0;ians.size();i){e(1.000000)/(k[i].count()*1.000000)*ans[i].size();}coutfixedsetprecision(4)e;return0;}如有错误还请指出。注. 我的洛谷账号即为 lonys本篇文章同步在洛谷专栏发布。