对于树的情况，记\(down_i\)为从\(i\)点出发往下走的期望长度，\(up_i\)为往上走的期望长度，dp一下即可
对于基环外向树的情况，因为环上最多\(20\)个点，暴力处理环上每个点往两边走的期望长度，dp一下即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
// <2878.cpp> - Mon Mar 6 14:27:38 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=100010; const int MAXM=200010; const int INF=1e9; int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM]; inline void add(int x,int y,int z){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z; } bool vis[MAXN],on[MAXN]; int f[MAXN],fa[MAXN],fb[MAXN]; int ht,h[MAXN]; void dfs(int x){ vis[x]=1; for(int i=b[x];i;i=next[i]){ if(to[i]==f[x])continue; if(vis[to[i]]){ if(ht)continue; for(int j=x;j!=to[i];j=f[j])on[h[++ht]=j]=1; h[++ht]=to[i];on[to[i]]=1; continue; } f[to[i]]=x; dfs(to[i]); } } void redfs(int x){ for(int i=b[x];i;i=next[i]){ if(to[i]==f[x]||on[to[i]])continue; f[to[i]]=x; fa[to[i]]++; fb[to[i]]=val[i]; redfs(to[i]); } } double down[MAXN],up[MAXN]; int s[MAXN]; void dfsdown(int x){ for(int i=b[x];i;i=next[i]){ if(to[i]==f[x]||on[to[i]])continue; dfsdown(to[i]);s[x]++; down[x]+=down[to[i]]+val[i]; } if(s[x])down[x]/=s[x]; } void dfsup(int x){ up[x]=(down[f[x]]*s[f[x]]+up[f[x]]*fa[f[x]]-down[x]-fb[x])/(s[f[x]]-1+fa[f[x]])+fb[x]; for(int i=b[x];i;i=next[i])if(to[i]!=f[x])dfsup(to[i]); } int main(){ int n=gi(),m=gi(); for(int i=1;i<=m;i++){ int x=gi(),y=gi(),z=gi(); add(x,y,z); } dfs(1); if(m==n-1){ redfs(1); dfsdown(1); for(int i=b[1];i;i=next[i])dfsup(to[i]); }else{ for(int i=1;i<=ht;i++){f[h[i]]=0;redfs(h[i]);} for(int i=1;i<=ht;i++)dfsdown(h[i]); for(int i=1;i<=ht;i++) for(int j=b[h[i]];j;j=next[j])if(to[j]==h[i%ht+1])fb[h[i%ht+1]]=val[j]; for(int i=1;i<=ht;i++){ int x=h[i]; double k=1; for(int j=i%ht+1;j!=i;j=j%ht+1){ int y=h[j],z=h[j%ht+1]; if(z==x)up[x]+=k*(fb[y]+down[y]); else up[x]+=k*(fb[y]+down[y]*s[y]/(s[y]+1)); k/=(s[y]+1); } k=1; for(int j=(i+ht-2)%ht+1,p=x;j!=i;j=(j+ht-2)%ht+1){ int y=h[j],z=h[(j+ht-2)%ht+1]; if(z==x)up[x]+=k*(fb[p]+down[y]); else up[x]+=k*(fb[p]+down[y]*s[y]/(s[y]+1)); k/=(s[y]+1); p=y; } up[x]/=2; fa[x]=2; for(int j=b[x];j;j=next[j]) if(!on[to[j]])dfsup(to[j]); } } double ans=0; for(int i=1;i<=n;i++)ans+=(down[i]*s[i]+up[i]*fa[i])/(s[i]+fa[i]); printf("%.5lf",ans/n); return 0; } |
说点什么