NOI 2012 【迷失游乐园】

游乐园】"/>

NOI 2012 【迷失游乐园】

这道题，额，反正我是刚了2天，然后就萎了。。。。。。（是不是觉得我很菜）

题目描述：

放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩。

进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有n个景点、m条道路的无向连通图，且该图中至多有一个环（即m只可能等于n或者n-1）。小Z现在所在的大门也正好是一个景点。小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小Z会一直游玩，直到当前景点的相邻景点都已经访问过为止。

小Z所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？

小Z把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

【评分方法】本题没有部分分，你程序的输出只有和标准答案的差距不超过0.01时，才能获得该测试点的满分，否则不得分。

数据范围：n<=100000，环中节点个数小于20,。

思路分析：

这题，怎么说呢？额，很恶心，嗯，没错，就是这样。

前两天，我没看题解，自己做，想了1个钟头思路就想出来了，但是代码调了两天还是错，第三天一看题解，发现需要注意的细节实在太多了，恶心的一批，调得我想杀人。。。

先将一下大体思路吧。

环中节点数小于20，很明显了，就是写一个基环树DP嘛，既然这样的话，我们就先来说一下一颗树的怎么写吧。

对于树上的一个节点，以它为出发点显然要分两种情况讨论：

1、往它的子树走（记作down操作）

2、往它的父亲走（记作up操作）

很明显可以用换根DP的方式来求解。状态：f[u]表示以u为起点，往u的子树走的期望长度，代码中的期望是没有算当前u节点影响的，其实你们也可以挑战一下直接表示期望的状态，反正我是挑战失败了，分类讨论写了一大堆，愣是没调出来。。。。。。先给大家说一说我为什么直接算期望难写吧，随便给大家举几个例子：

1、算f[u]要除以du[u]，而路径上的其他点都只要除以du[u]-1就够了（一条边是由父亲走过来的，所以不用算）。

2、du[u]-1=0，u是否在环上，在的话du[u]要-2。

3、做环的时候，出度要在du[u]-2,du[u]-1,du[u]之间来回变化，还要根据是否有子树来判断是否应该停止。

4、......

然后，我差点把编译器卸了。。。。。。

好，接着我们刚才的状态，转移很简单：

f[u]=[Σ_{v是u的儿子} (f[v]+dist[i])]/(du[u]-1)          若u为根则不用-1。（这个转移是直接表示期望）

d[u]=Σ_{v是u的儿子} (f[v]+dist[i])                                                         （这是没算u的，代码里d用了p代替，但最终的dp数组还是d）

那么以v为起点往上走应该怎么做呢？

考虑换根，我们先把以u（v的父亲）为起点的期望路径长度减去儿子v对u的贡献，然后把u剩下的部分当做v的一个子树，算出u对于v的贡献。

转移：d[v]=(d[u]-f[v]-dist[i])/max(1,du[u]-1)+dist[i]

重点来了，注意方程中的du[u]-1，这是我再第二天才发现并想通的，当时满怀希望地交了一发，结果成功的得到了50分的好成绩，拿到了“再写N个讨论还是WA”的奖励。。。

为什么是du[u]-1呢，不是以v为起点吗，那不应该是du[v]吗，怎么会是du[u]-1呢？

想想我们对于dp的定义，看看我们是从哪里转移过来的，定义告诉我们，u对于d[u]的影响我们是还没有算的，而v对于d[v]的影响我们是不用算的（会在最后统计答案时统一除去），那么很清楚这个我们要算的是u对于d[v]的影响，而不是v对于d[v]的影响，所以便是du[u]，而后面的那个-1就是因为u是从v走过来的，所以要除去u与v之间的连边。

在一颗树上的思路就是这样啦，很恶心不是吗？

那么恭喜你，当你处理完这么细节后，基环树上的dp过程中还有几个恶心的细节等着你去发现与处理。

先讲一下基环树dp的大体思路吧，对于环上的每一个点，都先对其对应子树跑一遍down操作。然后根据这些，算出每一个环上的点以它为起点的期望路径长度（也就是d[i]）。再对环上的每一个点，对其对应子树跑一遍up操作。

思路很简单，——开始处理细节吧，少年！！！

我们剩下要处理的便是如何根据这些算出每一个环上的点以它为起点的期望路径长度了。

以u为起点，遍历环中节点。

若点v是已经转完了大半圈，下一个访问的节点就是u了，那么du[v]就要-2，因为v之前的一个点不能走，下一个点u也不能走。若v不属于刚才那种情况，那么du[v]就-1，因为之前的那个点不能走。g[u]=[∑_{v与u相连，且未被访问}  (g[v]+dist[i])]/(du[u]-1或2)   注意如果节点v属于第1种情况则不能加dist[i]。

呼——，终于写完了！

写这篇题解的时候其实我一直都忘不了一开始被恶心细节统治的恐惧。。。。。。

代码实现：

varf,d,g,p:array[1..100000]of double;vis,cir:array[1..100000]of boolean;next,dist,vet:array[1..200000]of longint;head,du,fa:array[1..100000]of longint;i,n,m,x,y,z,tot,root:longint;ans:double;
function max(a,b:longint):longint;
beginif a>b then exit(a) else exit(b);
end;
procedure add(x,y,z:longint);
begininc(tot);next[tot]:=head[x];vet[tot]:=y;head[x]:=tot;dist[tot]:=z;
end;
procedure circle(u,father:longint);
vari,v:longint;
begini:=head[u]; vis[u]:=true;while i<>0 dobeginv:=vet[i];if (fa[u]<>v)and(vis[v]) thenbeginx:=u; fa[v]:=u;while not cir[x] dobegin cir[x]:=true; x:=fa[x]; end;end;if not vis[v] thenbegin fa[v]:=u; circle(v,u); end;i:=next[i];end;
end;
procedure down(u:longint);
vari,v:longint;
begini:=head[u]; vis[u]:=true;while i<>0 dobeginv:=vet[i];if (not vis[v])and(not cir[v]) thenbegindown(v);p[u]:=p[u]+f[v]+dist[i];inc(du[u]);end;i:=next[i];end;if du[u]>0 then f[u]:=p[u]/du[u];if u<>root then inc(du[u]);
end;
procedure up(u,father:longint);
vari,v:longint;
begini:=head[u];while i<>0 dobeginv:=vet[i];if (v<>father)and(not cir[v]) thenbegind[v]:=d[v]+(d[u]-f[v]-dist[i])/max(1,du[u]-1)+dist[i];            //du[u]-1要吃透up(v,u);end;i:=next[i];end;
end;
procedure dfs(u,father:longint);
vari,v,k:longint;flag:boolean;
begini:=head[u]; flag:=false; vis[u]:=true; d[u]:=0;while i<>0 dobeginv:=vet[i];if (v<>father)and(cir[v])and(v<>root) thenbeginflag:=true; dfs(v,u);d[u]:=d[u]+d[v]+dist[i];end;i:=next[i];end;if u=root then exit;                                            //恶心细节处理k:=max(1,du[u]);if flag then begin k:=du[u]+1; d[u]:=(d[u]+p[u])/k; endelse d[u]:=f[u];
end;
beginread(n,m);for i:=1 to m dobeginread(x,y,z);add(x,y,z); add(y,x,z);end;if n=m thenbegincircle(1,0);       //找环fillchar(vis,sizeof(vis),false);for i:=1 to n doif cir[i] then begin root:=i; down(i); end;for i:=1 to n doif cir[i] thenbegin root:=i; dfs(i,0); g[i]:=d[i]; end;for i:=1 to n do d[i]:=p[i];for i:=1 to n doif cir[i] then begin d[i]:=d[i]+g[i]; du[i]:=du[i]+2; end;for i:=1 to n doif cir[i] then up(i,0);for i:=1 to n doans:=ans+d[i]/du[i];writeln(ans/n:0:2);end elsebeginroot:=1;down(1);for i:=1 to n dod[i]:=p[i];up(1,0);for i:=1 to n doans:=ans+d[i]/du[i];writeln(ans/n:0:2);end;
end.

转载于:.html