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数组了，然后再分别下传到每个子树里。
1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 int flag,n,m,f[200005],len[200005],vis[200005],tot,go[200005],next[200005],cnt,cir[200005],huan[200005],first[200005],val[200005],du[200005]; 7 double down[200005],up[200005]; 8 int read(){ 9 char ch=getchar();int t=0,f=1; 10 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 11 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 12 return t*f; 13 } 14 void insert(int x,int y,int z){ 15 tot++; 16 go[tot]=y; 17 next[tot]=first[x]; 18 first[x]=tot; 19 val[tot]=z; 20 } 21 void add(int x,int y,int z){ 22 insert(x,y,z);insert(y,x,z); 23 } 24 void dfs1(int x,int fa){ 25 vis[x]=1; 26 for (int i=first[x];i;i=next[i]){ 27 int pur=go[i]; 28 if (vis[pur]) continue; 29 dfs1(pur,x); 30 down[x]+=(double)val[i]+(((double)down[pur])/((double)(du[pur]-1+(du[pur]==1)))); 31 } 32 } 33 void dfs2(int x,int fa){ 34 if (!cir[x]&&fa!=0) up[x]=len[x]+((double)((double)up[fa]+down[fa]-len[x]-((double)down[x])/((double)du[x]-1+(du[x]==1))))/((double)(du[fa]-1+(du[fa]==1))); 35 vis[x]=1; 36 for (int i=first[x];i;i=next[i]){ 37 int pur=go[i]; 38 if (vis[pur]) continue; 39 f[pur]=x; 40 len[pur]=val[i]; 41 dfs2(pur,x); 42 } 43 } 44 void work1(){ 45 dfs1(1,0); 46 for (int i=1;i<=n;i++) vis[i]=0; 47 dfs2(1,0); 48 double ans=0; 49 for (int i=1;i<=n;i++) ans+=((double)down[i]+(double)up[i])/((double)du[i]); 50 ans/=((double)(n)); 51 printf("%.5f ",ans); 52 } 53 void dfs(int x,int fa){ 54 vis[x]=1; 55 for (int i=first[x];i;i=next[i]){ 56 int pur=go[i]; 57 if (flag) return; 58 if (f[x]!=pur&&vis[pur]){ 59 len[pur]=val[i]; 60 int j=x; 61 while (j!=f[pur]){ 62 cnt++; 63 cir[j]=1; 64 huan[cnt]=j; 65 j=f[j]; 66 } 67 flag=1; 68 return; 69 }else if (!vis[pur]){ 70 len[pur]=val[i]; 71 f[pur]=x; 72 dfs(pur,x); 73 } 74 } 75 } 76 void work2(){ 77 flag=0; 78 dfs(1,0);cnt++; 79 for (int i=1;i<=n;i++) vis[i]=0; 80 for (int i=0;i<cnt;i++) vis[huan[i]]=1; 81 for (int i=0;i<cnt;i++) dfs1(huan[i],0); 82 for (int i=0;i<cnt;i++){ 83 int x=(i+1)%cnt;double s=1; 84 while (x!=i){ 85 if ((x+1)%cnt==i) up[huan[i]]+=(double)s*len[huan[(x-1+cnt)%cnt]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-2+(du[huan[x]]==2))); 86 else up[huan[i]]+=(double)s*len[huan[(x-1+cnt)%cnt]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-1)); 87 s=s/((double)(du[huan[x]]-1)); 88 x=(x+1)%cnt; 89 } 90 x=(i-1+cnt)%cnt;s=1; 91 while (x!=i){ 92 if ((x-1+cnt)%cnt==i) up[huan[i]]+=(double)s*len[huan[x]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-2+(du[huan[x]]==2))); 93 else up[huan[i]]+=(double)s*len[huan[(x)%cnt]]+((double)(s*down[huan[x]]))/((double)(du[huan[x]]-1)); 94 s=s/((double)(du[huan[x]]-1)); 95 x=(x-1+cnt)%cnt; 96 } 97 } 98 for (int i=1;i<=n;i++) vis[i]=0; 99 for (int i=0;i<cnt;i++) vis[huan[i]]=1; 100 for (int i=0;i<cnt;i++) dfs2(huan[i],0); 101 double ans=0; 102 for (int i=1;i<=n;i++) ans+=(down[i]+up[i])/(du[i]); 103 printf("%.5f ",ans/n); 104 } 105 int main(){ 106 cnt=-1; 107 n=read();m=read();flag=0; 108 for (int i=1;i<=m;i++){ 109 int x=read(),y=read(),z=read(); 110 add(x,y,z); 111 du[x]++;du[y]++; 112 } 113 if (m==n-1) work1(); 114 else work2(); 115 }