全国 做网站的企业,厦门做网站设计,软件技术一般在哪上班,南通网站建设价格正题
题目链接:https://www.luogu.com.cn/problem/P3343 题目大意
给出nnn个点的一张无向图#xff0c;每条边被修复的时间是[0,1][0,1][0,1]的一个随机实数#xff0c;求这张图联通期望时间。 1≤n≤10,m≤n(n−1)21\leq n\leq 10,m\leq \frac{n(n-1)}{2}1≤n≤10,m≤2n(n…正题
题目链接:https://www.luogu.com.cn/problem/P3343 题目大意
给出nnn个点的一张无向图每条边被修复的时间是[0,1][0,1][0,1]的一个随机实数求这张图联通期望时间。
1≤n≤10,m≤n(n−1)21\leq n\leq 10,m\leq \frac{n(n-1)}{2}1≤n≤10,m≤2n(n−1) 解题思路
这个随机实数好像是用来吓人的但是概率分布函数好像能搞
假设修好了kkk条之后恰好联通了那么期望需要的时间就是km1\frac{k}{m1}m1k
好了现在要求恰好在kkk条边修好之后联通的方案因为每条边修好的先后顺序是完全随机的。
设fS,if_{S,i}fS,i在生成子图SSS中修好了iii条边是没有联通的方案gS,ig_{S,i}gS,i则表示联通了的方案dSd_{S}dS表示生成子图SSS的边数。
求fS,if_{S,i}fS,i的话和之前的[集训队作业2013]城市规划思路很向考虑扩展出一个新的点kkk那么我们枚举一个包含kkk的联通块T(k∈T,T⊆S)T(k\in T,T\subseteq S)T(k∈T,T⊆S)然后合并这个联通块后其他的乱选就有方程 fS,i∑k∈T,T⊆S∑j0min{dT,i}gT,j×(dS−Ti−j)f_{S,i}\sum_{k\in T,T\subseteq S}\sum_{j0}^{min\{d_{T},i\}}g_{T,j}\times \binom{d_{S-T}}{i-j}fS,ik∈T,T⊆S∑j0∑min{dT,i}gT,j×(i−jdS−T) 然后gS,ig_{S,i}gS,i不需要专门的方程因为有fS,igS,i(dSi)f_{S,i}g_{S,i}\binom{d_S}{i}fS,igS,i(idS)
然后答案就是 ∑i0mim1(fG,i(dGi)−fS,i−1(dGi−1))1m1∑i0mfG,i(dGi)\sum_{i0}^{m}\frac{i}{m1}(\frac{f_{G,i}}{\binom{d_G}{i}}-\frac{f_{S,i-1}}{\binom{d_G}{i-1}})\frac{1}{m1}\sum_{i0}^m\frac{f_{G,i}}{\binom{d_G}{i}}i0∑mm1i((idG)fG,i−(i−1dG)fS,i−1)m11i0∑m(idG)fG,i
时间复杂度O(3nn2)O(3^nn^2)O(3nn2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N10;
ll n,m,e[1N],d[1N],g[1N][N*N/2],f[1N][N*N/2],C[51][51];
signed main()
{scanf(%lld%lld,n,m);for(ll i1;im;i){ll x,y;scanf(%lld%lld,x,y);x--;y--;e[(1x)|(1y)];}ll MS(1n);for(ll s0;sMS;s)for(ll ts;t;t(t-1)s)d[s]e[t];C[0][0]1;for(ll i1;i50;i)for(ll j0;j50;j)C[i][j](j?C[i-1][j-1]:0)C[i-1][j];for(ll s1;sMS;s){for(ll i0;id[s];i){ll ks-s;for(ll t(s-1)s;t;t(t-1)s)if(tk)for(ll j0;jmin(i,d[t]);j)f[s][i]g[t][j]*C[d[s-t]][i-j];g[s][i]C[d[s]][i]-f[s][i];}}double ans0;for(ll k0;km;k)ans(double)f[MS-1][k]/C[m][k];printf(%.6lf\n,ans/(double)(m1));return 0;
}
