首页 > 其他分享 >[SHOI2014] 概率充电器

[SHOI2014] 概率充电器

时间:2022-10-23 10:36:30浏览次数:59  
标签:head 概率 充电器 val int db num maxm SHOI2014

首先因为每个点的贡献都是 \(1\),所以求的就是概率。

每个点都有三种来电的原因:

  1. 自己发电
  2. 由儿子那边来电
  3. 由父亲那边来电

前两种好办,只要树形 DP 一次就够了。

第三种的话就需要重新做了。

设 \(f_{i}\) 为被充电的概率。

现在设 \(u\) 为父亲,\(v\) 为儿子,我们想要从父亲转移到儿子。

当前的 \(f_u\) 有一部分是从 \(v\) 直接转移过去的,所以不能直接算。

设 \(x\) 为 \(f_u\) 中不是 \(v\) 产生的贡献。

只要把 \(x\) 解出来就行了。

\(f_{u}=x+(1-x)\times f_v\times val_i\)。

这样就能计算 \(u\) 对 \(v\) 的贡献了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=500002;
const int maxm=1000020;
typedef double db;
int to[maxm],nxt[maxm],head[maxn],num;db val[maxm];
void add(int x,int y,db v){num++;to[num]=y;val[num]=v;nxt[num]=head[x];head[x]=num;}
int n,m;
db f[maxn];
void dfs1(int p,int fa)
{
	for(int i=head[p];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs1(to[i],p);
		f[p]+=(1-f[p])*val[i]*f[v];
	}
}
void dfs2(int p,int fa)
{
	for(int i=head[p];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		if(fabs(1-f[v]*val[i])<1e-8)
		{
			dfs2(to[i],p);
			continue;
		}
		f[v]+=(1-f[v])*(f[p]-f[v]*val[i])/(1-f[v]*val[i])*val[i];
		dfs2(to[i],p);
	}
}
int main()
{
//	freopen("p.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y,p;scanf("%d%d%d",&x,&y,&p);
		double q=p*0.01;
		add(x,y,q); add(y,x,q);
	}
	for(int i=1;i<=n;i++)
	{
		int p;scanf("%d",&p);
		f[i]=p*0.01;
	}
	dfs1(1,0);
	dfs2(1,0);
	db ans=0;
	for(int i=1;i<=n;i++)
		ans+=f[i];
	printf("%.6lf",ans);
}

标签:head,概率,充电器,val,int,db,num,maxm,SHOI2014
From: https://www.cnblogs.com/cc0000/p/16818031.html

相关文章

  • 随机过程及应用->概率论准备知识
    一、概率论准备知识1.1概率空间\(\sigma\)代数(事件体)可测空间\((\Omega,F)\)概率公理化定义非负性\(0\leP(A)\le1\)规范性\(P(\Omega)=1\)可列可加性(事......
  • POJ-1322 Chocolate(概率DP)
    ChocolateTimeLimit:2000MSMemoryLimit:65536KTotalSubmissions:9279Accepted:2417SpecialJudgeDescriptionIn2100,ACMchocolatewillb......
  • 深度学习与统计力学(VI) :通过概率模型进行“深度想象”
    谷歌和斯坦福最新合作综述报告,发表在物理学的顶级期刊“凝聚态物理年鉴”(AnnualReviewofCondensedMatterPhysics)。作者YasamanBahri,JonathanKadmon,JeffreyPenni......
  • 详解降维-主成分分析-概率角度(Probabilistic PCA)【白板推导系列笔记】
    教科书对PCA的推导一般是基于最小化重建误差或者最大化可分性的,或者说是通过提取数据集的结构信息来建模一个约束最优化问题来推导的。事实上,PCA还有一种概率形式的推导,那......
  • 详解降维-SVD角度看PCA和PCoA & 主成分分析-概率角度(Probabilistic PCA)【白板推导系列
    前一节说明了重构特征空间找什么方向的向量,本节讲的是如何重构特征空间,即通过特征分解(SVD) 对于中心化的数据矩阵$HX$进行SVD$$HX=U\SigmaV^{T}\quad\left{\begin{al......
  • 概率统计基础
    1.11.1.11.1.2两种基本类型:离散型和连续型离散型随机变量即在一定区间内变量取值为有限个或可数个伯努利分布、二项分布、几何分布、泊松分布、超几何分布等连续型随......
  • 概率生成函数 (PGF)
    1.概述取值处概率的生成函数。\(F(1)=1,F'(1)=E\)2.分析设\(F(i)\)为\(i\)时刻结束概率的生成函数,\(G(i)\)为\(i\)时刻未结束概率的生成函数,那么有:\[f_i+g_i=g......
  • 概率与期望
    (〇)写在前面的话所谓概率/期望题,本质上还是dp。实际上,在很多情况下,概率/期望与计数dp是一样的。(一)有限情况下的概率/期望这部分题目是与计数类dp最相关的。1.1关于古典......
  • 连续型随机变量:概率密度
    分布函数:https://www.cnblogs.com/tsuish/p/16731610.html分布函数的一些常用方法概率密度:(1)均匀分布(2)指数分布(3)正态分布......
  • 事件相机特征跟踪-概率数据关联法
    1、前言在特征跟踪时,有一个重要的概念是数据关联(DataAssociation)。所谓数据关联,可以理解为:哪些数据是由同一个源产生?对于传统图像而言,我们可以计算特征的描述子,进行匹配从......