【BZOJ 2878】 2878: [Noi2012]迷失游乐园 （环套树、树形概率DP）

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<set>
  7 using namespace std;
  8 #define Maxn 100010
  9 
 10 struct node
 11 {
 12     int x,y,next,o,c;
 13     bool p;
 14 }t[Maxn*2];int len;
 15 int first[Maxn];
 16 int n,m;
 17 
 18 void ins(int x,int y,int c)
 19 {
 20     t[++len].x=x;t[len].y=y;t[len].c=c;
 21     t[len].next=first[x];first[x]=len;
 22     t[len].p=1;
 23     if(len%2==0) t[len].o=len-1;
 24     else t[len].o=len+1;
 25 }
 26 
 27 int hw[Maxn],nw[Maxn],k[Maxn];
 28 bool vis[Maxn];
 29 bool ffind(int x,int f)
 30 {
 31     vis[x]=1;
 32     for(int i=first[x];i;i=t[i].next) if(t[i].p)
 33     {
 34         t[i].p=t[t[i].o].p=0;
 35         int y=t[i].y;
 36         if(vis[y]) {hw[++hw[0]]=y;nw[hw[0]]=t[i].c;hw[++hw[0]]=x;return 1;}
 37         if(ffind(y,x)) {nw[hw[0]]=t[i].c;hw[++hw[0]]=x;return 1;}
 38     }
 39     return 0;
 40 }
 41 
 42 double f[Maxn],g[Maxn];
 43 int son[Maxn];
 44 double ans=0;
 45 void dfs(int x,int ff)
 46 {
 47     f[x]=0;
 48     int cnt=0;
 49     for(int i=first[x];i;i=t[i].next) if(vis[t[i].y]&&t[i].y!=ff)
 50         cnt++;
 51     son[x]=cnt;
 52     for(int i=first[x];i;i=t[i].next) if(vis[t[i].y]&&t[i].y!=ff)
 53     {
 54         int y=t[i].y;
 55         dfs(y,x);
 56         f[x]+=(f[y]+t[i].c)/cnt;
 57     }
 58     ans+=f[x]*cnt/k[x]/n;
 59 }
 60 
 61 void dfs2(int x,int ff)
 62 {
 63     double tot=0;
 64     for(int i=first[x];i;i=t[i].next) if(vis[t[i].y]&&t[i].y!=ff)
 65         tot+=f[t[i].y]+t[i].c;
 66     for(int i=first[x];i;i=t[i].next) if(vis[t[i].y]&&t[i].y!=ff)
 67     {
 68         int y=t[i].y;
 69         if(k[x]==1)
 70         {
 71             if(ff==0) g[y]=g[x]+t[i].c;
 72             else g[y]=g[x]+t[i].c;
 73         }
 74         else
 75         {
 76             if(g[x]) g[y]=g[x]/(k[x]-1);
 77             if(son[x]>1) g[y]+=(tot-f[y]-t[i].c)/(k[x]-1);
 78             g[y]+=t[i].c;
 79         }
 80     }
 81     for(int i=first[x];i;i=t[i].next) if(vis[t[i].y]&&t[i].y!=ff)
 82         dfs2(t[i].y,x);
 83     ans+=g[x]/k[x]/n;
 84 }
 85 
 86 int main()
 87 {
 88     scanf("%d%d",&n,&m);
 89     len=0;
 90     memset(first,0,sizeof(first));
 91     for(int i=1;i<=m;i++)
 92     {
 93         int x,y,c;
 94         scanf("%d%d%d",&x,&y,&c);
 95         ins(x,y,c);ins(y,x,c);
 96     }
 97     for(int i=1;i<=n;i++)
 98     {
 99         k[i]=0;
100         for(int j=first[i];j;j=t[j].next) k[i]++;
101     }
102     hw[0]=0;
103     memset(vis,0,sizeof(vis));
104     ffind(1,0);
105     while(hw[hw[0]]!=hw[1]) hw[0]--;hw[0]--;
106     memset(vis,1,sizeof(vis));
107     for(int i=1;i<=hw[0];i++) vis[hw[i]]=0;
108     if(n-1==m)
109     {
110         dfs(1,-1);
111         g[1]=0;
112         dfs2(1,-1);
113     }
114     else
115     {
116         nw[0]=nw[hw[0]];
117         for(int i=1;i<=hw[0];i++)
118         {
119             dfs(hw[i],0);
120         }
121         for(int i=1;i<=hw[0];i++)
122         {
123             g[hw[i]]=0;
124             double p=1;
125             int hh=0;
126             for(int j=1;j<hw[0];j++)
127             {
128                 int y=(i-1+j)%hw[0]+1;
129                 hh+=nw[y-1];
130                 y=hw[y];
131                 if(j==hw[0]-1) g[hw[i]]+=p*(f[y]+hh);
132                 else g[hw[i]]+=p*(k[y]-2)/(k[y]-1)*(f[y]+hh);
133                 p/=k[y]-1;
134             }
135             p=1;hh=0;
136             for(int j=1;j<hw[0];j++)
137             {
138                 int y=(i-1-j+hw[0])%hw[0]+1;
139                 hh+=nw[y];
140                 y=hw[y];
141                 if(j==hw[0]-1) g[hw[i]]+=p*(f[y]+hh);
142                 else g[hw[i]]+=p*(k[y]-2)/(k[y]-1)*(f[y]+hh);
143                 p/=k[y]-1;
144             }
145         }
146         for(int i=1;i<=hw[0];i++)
147         {
148             dfs2(hw[i],0);
149         }
150     }
151     
152     printf("%.5lf\n",ans);
153     return 0;
154 }