[NOI2012]迷失游乐园

安利cnblog博客：[[Noi2012]迷失游乐园](https://www.cnblogs.com/Miracevin/p/9592243.html) 比较麻烦的图论期望题。 花费3hWA一次，然后AC了此题。 和网上的题解大致差不多。肯定也要分树形和基环树两种情况讨论。 ### 首先考虑树的： 本人没有用什么up数组。只有一个E[x]，P[x] 表示，从x往下走的期望长度。到点X的概率。 树 对于一棵树，直接dfs1，找到以1为根的信息。 然后换根即可。dfs2就是换根、。 ans[x]={ len[fa]+(ans[fa]-(E[x]/P[x]+len[fa])×1/d[fa])×d[fa]/(d[fa]-1) }×1/d[x] + E[x]/P[x] × (d[x]-1)/d[x] len[fa]表示，x到fa的边的长度。ans[i]表示，从i出发的期望长度。 貌似非常复杂。因为少记一个up嘛。 就是，算了两个部分，x向上走到fa的贡献，和向下走到儿子的贡献 前半部分向上走的： 算ans[fa]抛去x的部分：E[x]/P[x]，把x向下走的贡献变成P[x]=1的贡献，然后加上len[fa]，再乘上fa到x的概率，就是1/d[fa] 减掉之后，由于其他部分，从ans[x]出发，每个点的概率是1/d[fa]的，但是，现在fa不是根，变成了1/(d[fa]-1) 所以，后面乘了一个d[fa]/(d[fa]-1)，就变成了概率为1/(d[fa]-1)的情况。 再加上一个len[fa]，就是如果走到fa的贡献了。当然还要有一个概率1/d[x] 后半部分向下走的： E[x]/P[x]，把从x出发的概率变成1，由于现在到每一个儿子的概率不是1/(d[x]-1)了，可以往上走，就变成了1/d[x] 也要调整一下。 就可以换根啦！ ### 基环树： 　　环比较麻烦。从下面的树往上走不好考虑。 　　所以先处理环。 用一个栈dfs3找到所有的环上的点。是环上的点，记录进huan,共tot个。rac[i]=1,表示i是环上的点。 然后从这些环上点暴力dp，20n也不会TLE，找到ans[huan[i]] 环上暴力dp进入wrk函数。 钦定出发点st不能访问。发现，要么往左环上走，要么往右环上走，要么往下面的树走。 往树走直接dfs1即可。 往环走，发现，不经过st的情况下，也是遍历一个树诶！！！，只不过是“横躺”了环上的一部分 所以仍然可以dfs1处理。 然后，再对每一个环的每一个子树一遍dfs1，就得到了从这个子树的根（环点的一个儿子），往下走的E[x]了。 然后，对于每一个环上节点，分别往下换根。开始的时候，fa就是环上节点。 这是dfs4（其实和dfs2差不多） 换根的转移方程类似了。（不过，代码中是exp，传进来的时候其实就是ans[fa]） 两个值得注意的细节： 1.dfs3找环的时候，第一次vis[y]就fl=true之后vis[y]都不可能再是环了。（可能不是正经的找基环的方法） 2.dfs1的时候，为了确定儿子的选择方法，可以暴力算一下，方便之后的转移概率处理。 ## Code ```cpp #include<bits/stdc++.h> using namespace std; const int N=100000+5; int n,m; struct node{ int nxt,to,val; }e[2*N]; int hd[N],cnt; double E[N],P[N]; double ans[N]; double op; int d[N]; void add(int x,int y,int z){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].val=z; hd[x]=cnt; } bool vis[N]; int rt; void dfs1(int x,double to,int fa,int dis){//算子树期望 ，to是到这个点的概率，dis其实没用 E[x]=0.00; P[x]=to; double lv=0.0; int can=0; for(int i=hd[x];i;i=e[i].nxt){//注意这里，先暴力算一下能走几个儿子，避免概率算错。 int y=e[i].to; if(y==fa) continue; if(vis[y]) continue; can++; } if(can!=0) lv=1.00/((double)can);//走每个儿子的概率，不要除以0 for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; if(vis[y]) continue; dfs1(y,to*lv,x,dis+e[i].val); E[x]+=P[y]*(double)e[i].val+E[y];//注意，P[y]不要再乘E[y]了，传进去的时候，to*lv相当于已经乘过了 } } void dfs2(int x,double exp,int fa,int val){ if(x!=1){//麻烦的换根方程式，注意不要除以0 if(d[fa]!=1) exp=((double)val+(exp-(E[x]/P[x]+(double)val)*(1.00/(double)d[fa]))*((double)d[fa]/((double)d[fa]-1.00)))*(1.00/(double)d[x]); else exp=(double)val*(1.00/(double)d[x]); exp+=((double)E[x]/(double)P[x])*(((double)d[x]-1.00)/((double) d[x])); ans[x]=exp; } for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; dfs2(y,exp,x,e[i].val); } } int rac[N]; int huan[N],tot; int sta[N],top; bool fl=false; void dfs3(int x,int fa){ sta[++top]=x; vis[x]=1; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; if(vis[y]){ if(fl) continue; fl=true;//注意这个fl，保证第一次找到vis的情况（也就是环），就不会再进行了，因为回溯的时候，会再vis[y]==1一次 int z; do{ z=sta[top]; rac[z]=1; huan[++tot]=z; top--; }while(z!=y); } else dfs3(y,x); } if(sta[top]==x) top--; } void dfs4(int x,double exp,int fa,int val){//类似的基环树换根 if(d[fa]!=1) exp=((double)val+(exp-(E[x]/P[x]+(double)val)*(1.00/(double)d[fa]))*((double)d[fa]/((double)d[fa]-1.00)))*(1.00/(double)d[x]); else exp=(double)val*(1.00/(double)d[x]); exp+=((double)E[x]/(double)P[x])*(((double)d[x]-1.00)/((double) d[x])); ans[x]=exp; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; dfs4(y,ans[x],x,e[i].val); } } double wrk(int st){//计算基环树环点的ans memset(E,0,sizeof E); vis[st]=1; double ret=0.0; rt=0; if(rac[st]){ for(int i=hd[st];i;i=e[i].nxt){ int y=e[i].to; if(rac[y]){ dfs1(y,1.00/(double)d[st],st,e[i].val); ret+=P[y]*e[i].val+E[y]; } else{ dfs1(y,1.00/(double)d[st],st,e[i].val); ret+=P[y]*e[i].val+E[y]; } } } vis[st]=0; return ret; } int main() { scanf("%d%d",&n,&m);int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); d[x]++,d[y]++; } if(m==n-1){//是树 rt=1; dfs1(1,1.00,0,0); ans[1]=E[1]; dfs2(1,E[1],0,0); op=0; for(int i=1;i<=n;i++){ op+=(1.00/(double)n)*ans[i]; } printf("%.5lf",op); return 0; } else{//是基环树 dfs3(1,0); memset(vis,0,sizeof vis); for(int i=1;i<=tot;i++){ ans[huan[i]]=wrk(huan[i]); } memset(vis,0,sizeof vis); for(int j=1;j<=tot;j++){ int x=huan[j]; vis[x]=1; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(rac[y]) continue; dfs1(y,1.00,x,0); } } for(int j=1;j<=tot;j++){ int x=huan[j]; vis[x]=1; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(rac[y]) continue; dfs4(y,ans[x],x,e[i].val); } } for(int i=1;i<=n;i++){ op+=(1.00/(double)n)*ans[i]; } printf("%.5lf",op); return 0; } } ```