[BZOJ1778/Luogu2973][Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元,期望)

发布于 2018-03-27  7 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1778/Luogu2973][Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元,期望)

Description

奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。猪猡的文明包含1到N (2 <= N <= 300)一共N个猪城。这些城市由M (1 <= M <= 44,850)条由两个不同端点A_j和B_j (1 <= A_j<= N; 1 <= B_j <= N)表示的双向道路连接。保证城市1至少连接一个其它的城市。一开始臭气弹会被放在城市1。每个小时(包括第一个小时),它有P/Q (1 <= P <=1,000,000; 1 <= Q <= 1,000,000)的概率污染它所在的城市。如果这个小时内它没有污染它所在的城市,那麽它随机地选择一条道路,在这个小时内沿着这条道路走到一个新的城市。可以离开这个城市的所有道路被选择的概率均等。因为这个臭气弹的随机的性质,奶牛们很困惑哪个城市最有可能被污染。给定一个猪猡文明的地图和臭气弹在每个小时内爆炸的概率。计算每个城市最终被污染的概率。如下例,假设这个猪猡文明有两个连接在一起的城市。臭气炸弹从城市1出发,每到一个城市,它都有1/2的概率爆炸。 1--2 可知下面这些路径是炸弹可能经过的路径(最后一个城市是臭气弹爆炸的城市): 1: 1 2: 1-2 3: 1-2-1 4: 1-2-1-2 5: 1-2-1-2-1 ... 要得到炸弹在城市1终止的概率,我们可以把上面的第1,第3,第5……条路径的概率加起来,(也就是上表奇数编号的路径)。上表中第k条路径的概率正好是(1/2)^k,也就是必须在前k-1个回合离开所在城市(每次的概率为1 - 1/2 = 1/2)并且留在最后一个城市(概率为1/2)。所以在城市1结束的概率可以表示为1/2 + (1/2)^3 + (1/2)^5 + ...。当我们无限地计算把这些项一个个加起来,我们最后会恰好得到2/3,也就是我们要求的概率,大约是0.666666667。这意味着最终停留在城市2的概率为1/3,大约为0.333333333。

Tag

高斯消元,期望

题目大意

一个从一号点出发的炸弹,在每一个点有p/q的概率爆炸,否则随机选择一条出边移动。求在每一个点爆炸的概率。

解决思路

由全期望公式,设F[u]表示在第u个点爆炸的概率,那么对于与u相连的一个点v,有
\[F[u]=F[v]*(1-\frac{p}{q})*(v到u的路径条数)/(点v的度数)+[u是否是1号点]\]
由于F的转移顺序是不确定的,所以我们可以转化为n个n元一次方程组,高斯消元得到每一个F[i]。
由于对于每一个点的\(\frac{p}{q}\)都是一定的,那么记\(sum=\sum F[i]\),在第i个点爆炸的概率就是\(\frac{F[i]}{sum}\)

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1778/Luogu2973][Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元,期望)


HNCJ OIer 一枚