1 #include2 #include 3 #include 4 #define M 100005 5 #define ld long double 6 int head[M],next[10*M],u[10*M],l[10*M],n,m,cnt,du[M],v[M],root,now,fa[M],c[M]; 7 ld d[M],f[M],g[M],gg[M]; 8 using namespace std; 9 void jia(int a1,int a2,int a3) 10 { 11 cnt++; 12 u[cnt]=a2; 13 l[cnt]=a3; 14 next[cnt]=head[a1]; 15 head[a1]=cnt; 16 return; 17 } 18 void dfs1(int a1) 19 { 20 v[a1]=1; 21 for(int i=head[a1];i;i=next[i]) 22 if(!v[u[i]]&&!c[u[i]]) 23 { 24 dfs1(u[i]); 25 du[a1]++; 26 d[a1]+=f[u[i]]+(ld)l[i]; 27 } 28 if(du[a1]) 29 f[a1]=d[a1]/(ld)du[a1]; 30 if(a1!=root) 31 du[a1]++; 32 return; 33 } 34 void dfs2(int a1) 35 { 36 v[a1]=1; 37 for(int i=head[a1];i;i=next[i]) 38 if(!v[u[i]]&&!c[u[i]]) 39 { 40 int k=du[a1]-1; 41 if(!k) 42 k++; 43 d[u[i]]+=(d[a1]-f[u[i]]-(ld)l[i])/(ld)k+(ld)l[i]; 44 dfs2(u[i]); 45 } 46 return; 47 } 48 void zhao(int a1) 49 { 50 v[a1]=++now; 51 for(int i=head[a1];i;i=next[i]) 52 if(!v[u[i]]) 53 { 54 fa[u[i]]=a1; 55 zhao(u[i]); 56 } 57 else if(u[i]!=fa[a1]&&v[a1]>v[u[i]]) 58 { 59 c[u[i]]=1; 60 for(;a1!=u[i];) 61 { 62 c[a1]=1; 63 a1=fa[a1]; 64 } 65 } 66 return; 67 } 68 void huan(int a1,int fa) 69 { 70 bool kg=1; 71 g[a1]=0.00000; 72 for(int i=head[a1];i;i=next[i]) 73 if(c[u[i]]&&u[i]!=fa&&u[i]!=root) 74 { 75 kg=0; 76 huan(u[i],a1); 77 g[a1]+=g[u[i]]+(ld)l[i]; 78 } 79 if(a1==root) 80 return; 81 int k=du[a1]; 82 if(!k) 83 k++; 84 if(kg) 85 g[a1]=d[a1]/(ld)k; 86 else 87 { 88 k=du[a1]+1; 89 g[a1]=(g[a1]+d[a1])/(ld)k; 90 } 91 } 92 int main() 93 { 94 scanf("%d%d",&n,&m); 95 for(int i=1;i<=m;i++) 96 { 97 int a1,a2,a3; 98 scanf("%d%d%d",&a1,&a2,&a3); 99 jia(a1,a2,a3);100 jia(a2,a1,a3);101 }102 if(n==m+1)103 {104 root=1;105 dfs1(1);106 for(int i=1;i<=n;i++)107 v[i]=0;108 dfs2(1);109 }110 else111 {112 zhao(1);113 for(int i=1;i<=n;i++)114 v[i]=0;115 for(int i=1;i<=n;i++)116 if(c[i])117 {118 root=i;119 dfs1(i);120 }121 for(int i=1;i<=n;i++)122 if(c[i])123 {124 root=i;125 huan(i,0);126 gg[i]=g[i];127 }128 for(int i=1;i<=n;i++)129 if(c[i])130 {131 du[i]+=2;132 d[i]+=gg[i];133 }134 for(int i=1;i<=n;i++)135 v[i]=0;136 for(int i=1;i<=n;i++)137 if(c[i])138 dfs2(i);139 }140 double ans=0.00000;141 for(int i=1;i<=n;i++)142 ans+=d[i]/(ld)du[i];143 printf("%.5lf\n",ans/(double)n);144 return 0;145 }
基环树DP，先处理环外的子树，在递归处理环上的点。