NOI2012 迷失游乐园【基环树随机游走问题】-程序员宅基地

技术标签: 基环树  概率DP  

题目描述:

基环树/树,随机起点,随机游走,不能走重复点,有边权,问期望路径长度。
n ≤ 100000 n\le100000 n100000,环长 ≤ 20 \le 20 20
洛谷链接

题目分析:

f u f_u fu表示 u u u点向下走的期望长度, s o n u son_u sonu表示儿子个数:
f u = 1 s o n u ∑ v f v + w u , v f_u=\frac 1{son_u}\sum_v{f_v+w_{u,v}} fu=sonu1vfv+wu,v

对于不在基环树上的点,设它向上走(意味着不再进入子树)的期望长度为 g u g_u gu,它有唯一的父亲,但是父亲可能在基环树上,向上有两个方向,于是记 s f u sf_u sfu表示 u u u的不往子树走的选择数(=1或2),记 u u u的父亲为 k k k
g u = w k , u + f k ∗ s o n k − ( f u + w k , u ) + g k ∗ s f k s o n k − 1 + s f k g_u=w_{k,u}+{f_k*son_{k}-(f_u+w_{k,u})+g_k*sf_k\over son_{k}-1+sf_{k}} gu=wk,u+sonk1+sfkfksonk(fu+wk,u)+gksfk

基环树的 g g g表示的是第一步不往子树走的期望长度,枚举它走到环上的哪一个点开始进入子树,并根据期望的线性性,期望 = 走进每个子树的概率 * 期望长度 + 走过环上某条边的概率 * 环长:

g u = ∑ u 顺 时 针 走 第 i 个 点 P i ∗ ( f i ∗ s o n i s o n i + 1 + w i − 1 , i ) g_u=\sum_{u顺时针走第i个点}P_i*(\frac {f_i*son_i}{son_i+1}+w_{i-1,i}) gu=uiPi(soni+1fisoni+wi1,i)

P i P_i Pi表示走到第 i i i个点的概率, P i = P i − 1 ∗ 1 s o n i − 1 + 1 P_i=P_{i-1}*\frac 1{son_{i-1}+1} Pi=Pi1soni1+11
最后一个点因为不能继续在环上走所以贡献为 P e n d ∗ ( f e n d + w ) P_{end}*(f_{end}+w) Pend(fend+w)

顺逆时针分别加上后除以2即可,或者把 P 1 P_1 P1设为0.5。总复杂度 O ( n + 环 长 2 ) O(n+环长^2) O(n+2)

先算 f f f,再算环 g g g,最后算树 g g g,答案为 1 n ∑ i = 1 n f i ∗ s o n i + g i ∗ s f i s o n i + s f i \frac 1n\sum_{i=1}^n{f_i*son_i+g_i*sf_i\over son_i+sf_i} n1i=1nsoni+sfifisoni+gisfi

Code(注意不要除0):

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,sf[maxn],son[maxn],cir[maxn],len,dis[maxn],dep[maxn],fa[maxn];
bool onc[maxn];
double f[maxn],g[maxn];
int fir[maxn],nxt[maxn<<1],to[maxn<<1],w[maxn<<1],tot;
void line(int x,int y,int z){
    nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,w[tot]=z;}
void dfsf(int u,int ff){
    
	for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff&&!onc[v]) 
		dfsf(v,u),son[u]++,f[u]+=f[v]+w[i];
	if(son[u]) f[u]/=son[u];
}
void dfsg(int u,int ff){
    
	for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff&&!onc[v]){
    
		g[v]=w[i]+(son[u]-1+sf[u]? (f[u]*son[u]-(f[v]+w[i])+g[u]*sf[u])/(son[u]-1+sf[u]) : 0);
		sf[v]=1,dfsg(v,u);
	}
}
void dfscir(int u,int ff){
    
	dep[u]=dep[fa[u]=ff]+1;
	for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff){
    
		if(!dep[v]) dfscir(v,u);
		else if(dep[u]<dep[v]) for(;v!=fa[u];v=fa[v]) onc[cir[++len]=v]=1;
	}
}
#define Next(i) (i==len?1:i+1)
#define Pre(i) (i==1?len:i-1)
int main()
{
    
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),line(x,y,z),line(y,x,z);
	if(m==n-1) dfsf(1,0),dfsg(1,0);
	else{
    
		dfscir(1,0);
		for(int i=1;i<=len;i++) dfsf(cir[i],0);
		for(int i=1;i<=len;i++) for(int j=fir[cir[i]];j;j=nxt[j]) if(to[j]==cir[Next(i)]) {
    dis[i]=w[j];break;}
		for(int i=1;i<=len;i++){
    
			double P = 0.5; int u=cir[i];
			for(int j=Next(i),v;j!=i;P*=1./(son[v]+1),j=Next(j))
				v=cir[j], g[u]+=P*((son[v]?f[v]*son[v]/(son[v]+(Next(j)!=i)):0)+dis[Pre(j)]);
			P=0.5;
			for(int j=Pre(i),v;j!=i;P*=1./(son[v]+1),j=Pre(j))
				v=cir[j], g[u]+=P*((son[v]?f[v]*son[v]/(son[v]+(Pre(j)!=i)):0)+dis[j]);
		}
		for(int i=1;i<=len;i++) sf[cir[i]]=2,dfsg(cir[i],0);
	}
	double ans=0;
	for(int i=1;i<=n;i++) ans+=(f[i]*son[i]+g[i]*sf[i])/(son[i]+sf[i]);
	printf("%.8f\n",ans/n);
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/C20181220_xiang_m_y/article/details/106681808

智能推荐

90岁了,褚时健罕见反思:活着是为了什么?-程序员宅基地

文章浏览阅读378次。他,传统企业的爆品王,造酒、制糖、产烟,种橙子,干什么都是最好的。他,影响企业家的企业家,他的故事和创业精神,深深影响了中国企业界包括柳传志、王石等一些大佬,以及无数要为明天而奋斗的年轻人。他,就是褚时健。褚时健,这个曾被报告文学形容为像太阳一样灿烂的男人,淡然外表下的内心,似乎没有一个人能触碰到。观其容,听其语,你也许读不出跌宕起伏的人生,看不到在老人温暖笑容中刻下的沧桑,但一定不会忽略那亲自铸_90岁了,褚时健罕见反思

算法特训营第12周刷题题目-程序员宅基地

文章浏览阅读114次。算法特训营本周内容:1. 录播视频:树状数组,二维树状数组。2. 直播刷题题目:POJ2352、POJ3067、POJ3321、POJ1195。友情提示:以下是直播刷题链接(收费),不需要看直播请忽略。【直播地址】https://www.epubit.com/courseDetails?id=PCCbf16b01a6788&recommenderCode=1540556欢迎大家一起刷题。...

NBT:5万个基因组和1.2万个新种的地球微生物基因组集-程序员宅基地

文章浏览阅读3.6k次,点赞4次,收藏14次。地球微生物组的基因组集A genomic catalog of Earth’s microbiomesNature Biotechnology [IF:36.558]2020-11-09..._ani 新属

algorithm第三周作业 Collinear Points_algorithm i collinear points-程序员宅基地

文章浏览阅读889次,点赞2次,收藏2次。cousera 上algorithm part I第三周课程讲述的是排序,包括插入排序、选择排序、希尔排序、归并排序和快速排序。其配套作业为Collinear Points,题目大意为给定若干点,求出其中的有四个及以上点共线的线段。要求提交三个文件,Point.java,BruteCollinearPoints.java,FastCollinearPoints.java。Point类给定的的..._algorithm i collinear points

window.location.hash使用总结_$(window).bind('hashchange',-程序员宅基地

文章浏览阅读7.7k次。如果a的name和页面中某个元素的id同名的话,在Safari、Chrome浏览器中会跳到id元素的位置,在IE中则会跳到a元素的位置可以使用jQuery的haschange事件来侦听浏览器点击后退时的hash变化的事件.$(window).bind('hashchange', function () { //});不过以上方案在IE浏览器只能支持到IE8_$(window).bind('hashchange',

[C#]替换字符串中的斜杠和反斜杠_c# 替换斜杠-程序员宅基地

文章浏览阅读6.8k次,点赞2次,收藏2次。含有斜杠的字符串 中的 斜杠 替换为 反斜杠... string a = "X:\Data Backup\UnityProjects\TestAssetBundle\Assets";//Application.dataPath a = a.Replace("\\", "/");...显示结果X:/Data Backup/UnityProjects/TestAssetBundle/Assets..._c# 替换斜杠

随便推点

Serverless 框架之Kubeless 实战-(一)安装-程序员宅基地

文章浏览阅读1.4k次。1. 创建命名空间,创建kubeless 控制管理容器>kubectl create ns kubeless#自行安装方便切换空间的kubens>kubens kubeless#根据官方提供的yaml ,创建Kubeless Controller Manager容器:>kubectl create -f https://github.com/kubeless/kubeless/releases/download/v1.0.7/kubeless-non-rbac-v1.0..._kubeless

linux eclipse设置颜色,Linux Eclipse美化:解决工具栏过大和 Javadoc背景色修改-程序员宅基地

文章浏览阅读154次。Eclipse 在Ubuntu 下总是感觉上面的工具栏感觉特别的大,控件之间的空隙非常的大,和在Windows 下的感觉非常的不一样(毕竟是刚刚从windows叛逃出来),其实也不光光是Eclipse 是这样,其他也软件也同样有这个问题。尝试过通过更换主题来解决这样的问题,老是看着一个主题,审美总是会疲劳的。在网上找来一圈,解决方案:修改或者新建(系统默认是没有的)/home/Your_usern..._eclipse toolbar颜色

python基本图形绘制第二周答案_考试 嵩天老师 :测验2: Python语法程序与设计(第2周)...-程序员宅基地

文章浏览阅读1.1k次。测验2: Python基本图形绘制 (第2周)单项选择题1、哪个选项不能正确引用turtle库进而使用setup()函数?A、import turtle as tB、import setup from turtleC、from turtle import*D、import turtle正确答案 Bimport只有三种使用方法,以turtle库为例:import turtlefrom turtle ..._00390037003900301688536597255哪个选项不能正确引用turtle库进而使用setup()函数

[蓝桥杯2018初赛]乘积尾零(思路)_乘积尾零思想-程序员宅基地

文章浏览阅读343次。说实话,刚开始想简单了,只考虑了每个数的最后一位,但是没想到还能因式分解,每个数的因子里的2的个数和5的个数需要统计一下,因为2*5==0#include<stdio.h>#include<queue>#include<math.h>#include<map>#include<iostream>#include<string>#include<algorithm>#include<sstream>._乘积尾零思想

Verilog HDL——移位运算符_verilog左移运算符-程序员宅基地

文章浏览阅读8.3w次,点赞10次,收藏34次。Verilog HDL学习笔记——语法_verilog左移运算符

Linux Samba服务主配文件smb.conf中文详解_smb.conf中的printcap name是什么作用-程序员宅基地

文章浏览阅读243次。@TOC从网上找到描述比较详细的smb.conf中文解释:服务名:smb配置目录:/etc/sabma/主配置文件:/etc/sabma/smb.conf#============================== Global Settings =============================[global]samba服务器的全局设置,对整个服务器有效。workgrou..._smb.conf中的printcap name是什么作用