传送门
Description
基环树上随机选择一个点做起点，等概率向其相邻的节点移动，保证每个点只经过不超过(1)次
求期望的最大游走距离
Solution
假设环处在最上面的位置
设(down_x)表示向下走的期望距离，(up_x)表示向上走的期望距离
那么如果是树的话
[down_x=sum frac{w(E<x,son_i>)+down_{son_i}}{degree_x-1} ][up_x=frac{up_{fa}+down_{fa}*(degree_{fa}-1-w(E<x,fa>)-down[x])}{degree_{fa}-1} ]对于环，其实求(down_x)的部分是不会变得
考虑如果求得了环上每个点的(up)，那么外向树上的点(up)值可以类似树的方式求得
对于环上一个点：
首先它有可能往逆时针或顺时针走，概率相等
对于一个方向，它有可能顺着环走到一个点后开始向下走，进入该点的子树
求出到这个点的概率，再乘上它的(down)值
Code
#include<bits/stdc++.h>
#define reg register
#define db double
inline int read()
{
reg int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int MN=1e5+5;
int N,M,d[MN],son[MN];
struct edge{int to,w,nex;}e[MN<<1];
int hr[MN],en;
void ins(int x,int y,int w)
{
e[++en]=(edge){y,w,hr[x]};hr[x]=en;
e[++en]=(edge){x,w,hr[y]};hr[y]=en;
}
db down[MN],up[MN],ans;
bool vis[MN],inr[MN],flag;
int st[MN],last[MN],tp,cir[MN],num;
void tj(int x,int f)
{
if(flag) return;
vis[x]=true;st[tp++]=x;reg int i;
for(i=hr[x];i;i=e[i].nex) if(f^e[i].to&&!flag)
if(!vis[e[i].to]) last[e[i].to]=e[i].w,tj(e[i].to,x);
else
{
last[e[i].to]=e[i].w;
for(;st[tp]!=e[i].to;--tp)
inr[cir[num++]=st[tp-1]]=true;
flag=true;
return;
}
if(st[tp-1]==x) --tp;
}
void dfs1(int x,int f)
{//down
reg int i;
for(i=hr[x];i;i=e[i].nex)if((f^e[i].to)&&!inr[e[i].to])
++son[x],dfs1(e[i].to,x),down[x]+=e[i].w+down[e[i].to];
if(son[x])down[x]/=(db)son[x];
}
int Rt;
void dfs2(int x,int f,int len=0)
{//up
reg int i;
if(x!=Rt) up[x]=len+(db)(up[f]*(d[f]-son[f])+down[f]*son[f]-len-down[x])/(db)(d[f]>1?d[f]-1:1);
for(i=hr[x];i;i=e[i].nex)if((f^e[i].to)&&!inr[e[i].to]) dfs2(e[i].to,x,e[i].w);
}
int main()
{
N=read();M=read();reg int i,j,x,y;
for(i=1;i<=M;++i) x=read(),y=read(),ins(x,y,read()),++d[x],++d[y];
if(M==N-1) dfs1(1,0),dfs2(Rt=1,0);
else
{
tj(1,0);for(i=0;i<num;++i) dfs1(cir[i],0);
for(i=0;i<num;++i)
{
db p1=.5,p2=.5,s1=(db)last[cir[i]],s2=0.;
for(j=1;j<num;++j)
{
x=(i+j)%num;y=(i-j+num)%num;
s2+=(db)last[cir[y]];
if(j==num-1)
{
up[cir[i]]+=p1*(s1+down[cir[x]]);
up[cir[i]]+=p2*(s2+down[cir[y]]);
break;
}
up[cir[i]]+=p1*((db)son[cir[x]]/(db)(d[cir[x]]-1))*(s1+down[cir[x]]);
p1*=1./(d[cir[x]]-1);
up[cir[i]]+=p2*((db)son[cir[y]]/(db)(d[cir[y]]-1))*(s2+down[cir[y]]);
p2*=1./(d[cir[y]]-1);
s1+=(db)last[cir[x]];
}
}
for(i=0;i<num;++i) dfs2(Rt=cir[i],0);
}
for(i=1;i<=N;++i)
ans+=(up[i]*(db)(d[i]-son[i])+down[i]*(db)son[i])/(db)d[i];
ans/=(db)N;
printf("%.5lf
",ans);
return 0;
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！