放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有n个景点、m条道路的无向连通图，且该图中至多有一个环（即m只可能等于n或者n-1）。小Z现在所在的大门也正好是一个景点。小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小Z会一直游玩，直到当前景点的相邻景点都已经访问过为止。小Z所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？小Z把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。
第一行是两个整数n和m，分别表示景点数和道路数。 接下来行，每行三个整数Xi, Yi, Wi，分别表示第i条路径的两个景点为Xi, Yi，路径长Wi。所有景点的编号从1至n，两个景点之间至多只有一条道路。
共一行，包含一个实数，即路径的期望长度，保留五位小数
1 #include<cstdio> 2 #define ld long double 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 const int N=100010; 7 struct ee{int to,next,w;}e[N*10]; 8 int n,m,u,v,w,cnt,root,timer; 9 int head[N],du[N],vis[N],fa[N]; 10 ld f[N],gg[N],g[N],d[N]; 11 bool c[N]; 12 void ins(int u,int v,int w){ 13 e[++cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt; 14 e[++cnt].to=u;e[cnt].next=head[v];e[cnt].w=w;head[v]=cnt; 15 } 16 void dfs1(int x){ 17 vis[x]=1; 18 for (int i=head[x];i;i=e[i].next){ 19 int v=e[i].to; 20 if (!vis[v]&&!c[v]){ 21 du[x]++; 22 dfs1(v); 23 d[x]+=f[v]+e[i].w; 24 } 25 } 26 if (du[x]) f[x]=(d[x]+0.0)/du[x]; 27 if(x!=root) du[x]++; 28 } 29 30 void dfs2(int x){ 31 vis[x]=1; 32 for(int i=head[x];i;i=e[i].next){ 33 int v=e[i].to; 34 if(!vis[v]&&!c[v]){ 35 d[v]+=(d[x]-f[v]-e[i].w)/max(1,(du[x]-1))+e[i].w; 36 dfs2(v); 37 } 38 } 39 } 40 41 void find(int x){ 42 vis[x]=++timer; 43 for (int i=head[x];i;i=e[i].next){ 44 int v=e[i].to; 45 if(!vis[v]) fa[v]=x,find(v); 46 else if(fa[x]!=v&&vis[v]<vis[x]){ 47 c[v]=1; 48 for(;x!=v;) 49 c[x]=1,x=fa[x]; 50 } 51 } 52 } 53 54 void solve_cycle(int x,int fa){ 55 bool flag=1; 56 g[x]=0;//1 wa 57 for (int i=head[x];i;i=e[i].next){ 58 int v=e[i].to; 59 if(v!=root&&v!=fa&&c[v]){ 60 flag=0; 61 solve_cycle(v,x); 62 g[x]+=g[v]+e[i].w; 63 } 64 } 65 if(x==root) return; 66 int k=du[x];if(!k)k++; 67 if(flag)g[x]=(d[x]+0.0)/k; 68 else k=du[x]+1,g[x]=(g[x]+d[x])/k; 69 } 70 71 int main(){ 72 scanf("%d%d",&n,&m); 73 for (int i=1;i<=m;i++){ 74 scanf("%d%d%d",&u,&v,&w); 75 ins(u,v,w); 76 } 77 if(m==n-1){ 78 root=1; 79 dfs1(1); 80 memset(vis,0,sizeof(vis)); 81 dfs2(1); 82 }else{ 83 find(1); 84 memset(vis,0,sizeof(vis)); 85 for (int i=1;i<=n;i++) if(c[i]) { 86 root=i; 87 dfs1(i); 88 } 89 for (int i=1;i<=n;i++) if(c[i]) { 90 root=i; 91 solve_cycle(i,0); 92 gg[i]=g[i]; 93 } 94 memset(vis,0,sizeof(vis)); 95 for(int i=1;i<=n;i++) if(c[i]){ 96 du[i]+=2; 97 d[i]+=gg[i]; 98 } 99 for(int i=1;i<=n;i++) if(c[i]) dfs2(i); 100 } 101 double ans=0; 102 for (int i=1;i<=n;i++) ans+=(d[i]+0.0)/du[i]; 103 printf("%.5lf\n",ans/n); 104 }
原文：http://www.cnblogs.com/wuminyan/p/5191637.html