2、【輸出格式】輸出文件flood.out僅包含一行，即所有村莊注二塵的概率，保留小數(shù)點(diǎn)后三位?！緲永斎搿?3I20.2130.5230.7【樣例輸出】0.550【提示】乘法公式：如果兩個(gè)獨(dú)立事件A和B發(fā)生的概率是P(A)和P(B),則兩個(gè)事件同時(shí)發(fā)生的概率是P(A)XP(B)加法公式：如果兩個(gè)互斥(不可能同時(shí)發(fā)生的)事件A和B發(fā)生的概率是P(A)和P(B),則兩個(gè)事件恰好有一個(gè)發(fā)生的概率是P(A)+P(B)解題報(bào)告【邊搜索法】這是最容易想到的方法。設(shè)有m條邊ei,e2,env其被沖毀的概率是C(cj,c2,cm)o設(shè)X為m維向量X=(xi,X2,??,xm),每個(gè)X
3、j(l<=i<=m)都只能取0或者1。定義x*c二冇％心)，其中叫,心)二[：‘"當(dāng):y：=
4、U一ci^xi=u)形象的說(shuō)Xi就表示ei這條邊到底是保留還是不保留。定義G(X)為一個(gè)圖。它的定點(diǎn)集是{l..n},它的邊集是由那些滿足Xi=l的&組成的。(通俗的講G(X)fc是X代表的邊組成的子圖)定義Connect[X]表示G(x)是否連通，若連通Connect[X]=l>否則Connect[X]=Oo那么整個(gè)圖保持連通的概率是：工(X*C)Connect[X]X算法實(shí)現(xiàn)可以枚舉XI,X2,…,xm,采用并查集加邊的方法。此算法的時(shí)間復(fù)雜度是0(29。如果算O(m
5、)=O(n2),那么復(fù)雜度就是0(2?即便是nv=8這么小的數(shù)據(jù)范圍，恐怕也難以勝任。有一個(gè)小優(yōu)化。設(shè)X
6、,X2,…,Xk?l已經(jīng)確定，并口圖已經(jīng)連通了，那么不論Xk~Xm如何取值，都肯定滿足Connect[X]=k因此剩下的就不要枚舉了，因?yàn)樗麄兊目偢怕实扔?。加入此優(yōu)化之后對(duì)于n=8的數(shù)據(jù)都能夠達(dá)到瞬間岀解。但是這種雕蟲(chóng)小技治標(biāo)不治木，對(duì)復(fù)雜度也沒(méi)有木質(zhì)的貢獻(xiàn)。我們應(yīng)該考慮令辟蹊徑?！緞澐址ā苛頲[x,y]表示x點(diǎn)和y點(diǎn)之間的邊被沖毀的概率是多少(如果沒(méi)有邊就是1)0從問(wèn)題的反面考慮，即：圖不連通的概率是多少？如果圖不連通，必然被分成幾個(gè)連通分量一一也就是一個(gè)“
7、劃分”。定義G(S)為點(diǎn)集S的導(dǎo)出子圖。f(S)表示G(S)保持連通的概率。我們耍求的就是f({l..n})o定義min(S)表示S中的最小元素。現(xiàn)在考慮S不連通的概率。min(S)必然要屬于某一個(gè)連通分量，不妨設(shè)這個(gè)連通分量為Xo這吋候有幾點(diǎn)要保證：?X要連通?X中的點(diǎn)和非X中的點(diǎn)不能有邊和連。因此min(S)屬于某一個(gè)特定X的概率就是：f(X)*MUL(X,S?X)。其中MUL(A,B)=口5,,通俗的講就是連接A集合和B集合的所有邊的同時(shí)被沖毀的概率。于是：/(S)=1-工/(X)*MUL(X,S-X)XuS,min(S)eX如果定義M(S)表示S的導(dǎo)出子圖內(nèi)
8、部所有邊的乘積，則MUL(A,B)二MUL(A+B)?MUL(A)?MUL(B)。所以：f(S)=l-工/(X)*(M(S)—M(X)-M(S—X))XuS.min(S)eX至此問(wèn)題基本解決了。下面分析復(fù)雜度。設(shè)L=
9、S
10、,那么滿足條件的X集合不超過(guò)2^個(gè)。所以計(jì)算f(S)的吋間復(fù)雜度是：L=0M的計(jì)算也很簡(jiǎn)單。若
11、S
12、<2,則M(S)=Oo若
13、S
14、>=2,任取x,yes,則M(S)=c[x,y]*M(S-{x})*M(S-{y})/M(S-{x,y})o所以計(jì)算M的復(fù)雜度是2"。算法總復(fù)雜度是O(3n+2n)o空間復(fù)雜度是O(2n)o對(duì)于nv=8來(lái)說(shuō)，已經(jīng)綽綽有余
15、。即使n達(dá)到15,也可以應(yīng)付。
