BZOJ 2878 迷失游乐园

http://www.lydsy.com/JudgeOnline/problem.php?id=2878

题意:n个点的图，保证图联通，有n-1或者n条边，求从任意一个点出发，不经过相同点，最终无路可走的路径长度期望。

思路:m=n-1时，可以用dp，处理出i点往下，i点往上走的路径长度期望，然后O(n)统计就可以了。

m=n时，由于环上点点数不超过20，那这就是基环树，我们考虑枚举基环树上面的点i，假设我们到了i，并走向了i的子树。

这样我们就把环断开了，然后我们再两遍顺逆走这个环，就可以处理出up数组了，然后再分别下传到每个子树里。

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 int flag,n,m,f[],len[],vis[],tot,go[],next[],cnt,cir[],huan[],first[],val[],du[];

 double down[],up[];

 int read(){

     char ch=getchar();int t=,f=;

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void insert(int x,int y,int z){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

     val[tot]=z;

 }

 void add(int x,int y,int z){

     insert(x,y,z);insert(y,x,z);

 }

 void dfs1(int x,int fa){

     vis[x]=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (vis[pur]) continue;

         dfs1(pur,x);

         down[x]+=(double)val[i]+(((double)down[pur])/((double)(du[pur]-+(du[pur]==))));

     }

 }

 void dfs2(int x,int fa){

     if (!cir[x]&&fa!=) up[x]=len[x]+((double)((double)up[fa]+down[fa]-len[x]-((double)down[x])/((double)du[x]-+(du[x]==))))/((double)(du[fa]-+(du[fa]==)));

     vis[x]=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (vis[pur]) continue;

         f[pur]=x;

         len[pur]=val[i];

         dfs2(pur,x);

     }

 }

 void work1(){

     dfs1(,);

     for (int i=;i<=n;i++) vis[i]=;

     dfs2(,);

     double ans=;

     for (int i=;i<=n;i++) ans+=((double)down[i]+(double)up[i])/((double)du[i]);

     ans/=((double)(n));

     printf("%.5f\n",ans);

 }

 void dfs(int x,int fa){

     vis[x]=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (flag) return;

         if (f[x]!=pur&&vis[pur]){

             len[pur]=val[i];

             int j=x;

             while (j!=f[pur]){

                 cnt++;

                 cir[j]=;

                 huan[cnt]=j;

                 j=f[j];

             }

             flag=;

             return;

         }else if (!vis[pur]){

             len[pur]=val[i];

             f[pur]=x;

             dfs(pur,x);

         }

     }

 }

 void work2(){

      flag=;

      dfs(,);cnt++;

      for (int i=;i<=n;i++) vis[i]=;

      for (int i=;i<cnt;i++) vis[huan[i]]=;

      for (int i=;i<cnt;i++) dfs1(huan[i],);

      for (int i=;i<cnt;i++){

             int x=(i+)%cnt;double s=;

             while (x!=i){

                 if ((x+)%cnt==i) up[huan[i]]+=(double)s*len[huan[(x-+cnt)%cnt]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-+(du[huan[x]]==)));

                 else up[huan[i]]+=(double)s*len[huan[(x-+cnt)%cnt]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-));

                 s=s/((double)(du[huan[x]]-));

                 x=(x+)%cnt;

             }

             x=(i-+cnt)%cnt;s=;

             while (x!=i){

                 if ((x-+cnt)%cnt==i) up[huan[i]]+=(double)s*len[huan[x]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-+(du[huan[x]]==)));

                 else up[huan[i]]+=(double)s*len[huan[(x)%cnt]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-));

                 s=s/((double)(du[huan[x]]-));

                 x=(x-+cnt)%cnt;

             }

     }

     for (int i=;i<=n;i++) vis[i]=;

     for (int i=;i<cnt;i++) vis[huan[i]]=;

     for (int i=;i<cnt;i++) dfs2(huan[i],);

     double ans=;

     for (int i=;i<=n;i++) ans+=(down[i]+up[i])/(du[i]);

     printf("%.5f\n",ans/n);

 }

 int main(){

     cnt=-;

     n=read();m=read();flag=;

     for (int i=;i<=m;i++){

         int x=read(),y=read(),z=read();

         add(x,y,z);

         du[x]++;du[y]++;

     }

     if (m==n-) work1();

     else work2();

 }

巴特西

BZOJ 2878 迷失游乐园

最新文章

热门文章