235D Graph Game-白红宇

235D Graph Game

阅读量：6925 次

发布时间：2019-06-27

本文共 1547 字，大约阅读时间需要 5 分钟。

题目大意

分析

我们先考虑它是树的情况

我们设$event(x,y)$表示删除点x是y与x联通这件事对答案贡献的期望

我们设x到y这一条链的长度为$len$，$x$和$y$所属联通块的大小为$n$

则我们可以猜测$event$的值为$\frac{1}{len}$

我们可以用数学归纳法证明

我们知道直接选到$x$的概率为$\frac{1}{n}$

先选到其它点再通过若干步选到x的概率为$\frac{n-len}{n} * \frac{1}{len}$

由此得证

于是我们在考虑它是基环树的情况

我们不难发现对于不经过环的路径没有影响

而其它路径我们把它不经过环的那些距离设为$x$，经过环的两条路分别为$y$和$z$

$event(x,y)$发生的概率实际上就是这两条路中$x$是任意一条路上第一个被删除的结点的概率

我们再容斥一下就可以得到$event(x,y) = \frac{1}{x+y} + \frac{1}{x+z} - \frac{1}{x+y+z}$

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;int n,m,dep[5000],id[5000],cnt,sum,acc[5000],lca[3020][3020],f[5000];int dfn[5000],low[5000],ist[5000],belong[5000],tot[5000],maxid;double Ans;stack
                   
                    a;vector
                    
                     v[5000];inline void tarjan(int x,int fa){ dfn[x]=low[x]=++cnt; a.push(x); ist[x]=1; for(int i=0;i
                     
                      1)dfs(v[x][i],x); }}int main(){ int i,j,k,x,y; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d",&x,&y); x++,y++; v[x].push_back(y); v[y].push_back(x); } for(i=1;i<=n;i++) if(!dfn[i])tarjan(i,0); for(i=1;i<=n;i++) if(tot[belong[i]]>1){ id[i]=1; maxid=tot[belong[i]]; dfs(i,0); break; } for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(acc[i]==acc[j])Ans+=1.0/(dep[i]+dep[j]-2*dep[lca[i][j]]+1); else { int x=dep[i]+dep[j],y=abs(id[acc[i]]-id[acc[j]])-1,z=maxid-y-2; Ans+=1.0/(x+y)+1.0/(x+z)-1.0/(x+y+z); } } printf("%0.7lf\n",Ans); return 0;}