文档介绍：试题描述
洪水()
乡下有n(n<=8)个小村庄,用m条双向道路连接起来,每两个村庄最多用一条道路直接连接。最近村庄闹涝灾,洪水让这些道路各有一定的概率被淹没,而这些道路被淹没与否是相互独立的。你的任务是计算出所有村庄连在一起(即:从任意一个村庄都可以经过未被淹没的道路到达其他所有村庄)的概率有多大。
【输入格式】
, m,表示村庄的个数和道路的个数。以下m行每行有三个数i, j, p,即有一条连接村庄i和村庄j的双向道路(1<=i< j<=n),被洪水淹没的概率是p。,保留1位小数。
【输出格式】
,即所有村庄连在一起的概率,保留小数点后三位。
【样例输入】
3 3
1 2
1 3
2 3
【样例输出】
【提示】
乘法公式:如果两个独立事件A和B发生的概率是P(A)和P(B),则两个事件同时发生的概率是P(A)×P(B)
加法公式:如果两个互斥(不可能同时发生的)事件A和B发生的概率是P(A)和P(B),则两个事件恰好有一个发生的概率是P(A)+P(B)
解题报告
【边搜索法】
这是最容易想到的方法。
设有m条边e1,e2, …, em,其被冲毁的概率是C(c1, c2, …, cm)。设X为m维向量X=(x1, x2, .., xm),每个xi(1<=i<=m)都只能取0或者1。
定义X*C =,其中
形象的说xi就表示ei这条边到底是保留还是不保留。
定义G(X)为一个图。它的定点集是{1..n},它的边集是由那些满足xi=1的ei组成的。(通俗的讲G(X)就是X代表的边组成的子图)
定义Connect[X]表示G(x)是否连通,若连通Connect[X]=1、否则Connect[X]=0。
那么整个图保持连通的概率是:
算法实现可以枚举x1, x2, …, xm,采用并查集加边的方法。
此算法的时间复杂度是O(2m)。如果算O(m)=O(n2),那么复杂度就是O(2n*n)即便是n<=8这么小的数据范围,恐怕也难以胜任。
有一个小优化。
设x1, x2, …, xk-1已经确定,并且图已经连通了,那么不论xk ~ xm如何取值,都肯定满足Connect[X]=1。因此剩下的就不要枚举了,因为他们的总概率等于1。
加入此优化之后对于n=8的数据都能够达到瞬间出解。
但是这种雕虫小技治标不治本,对复杂度也没有本质的贡献。我们应该考虑令辟蹊径。
【划分法】
令c[x, y]表示x点和y点之间的边被冲毁的概率是多少(如果没有边就是1)。
从问题的反面考虑,即:图不连通的概率是多少?如果图不连通,必然被分成几个连通分量——也就是一个“划分”。
定义G(S)为点集S的导