Description

T國(guó)有N個(gè)城市，用若干雙向道路連接。一對(duì)城市之間至多存在一條道路。
在一次洪水之后，一些道路受損無(wú)法通行。雖然已經(jīng)有人開(kāi)始調(diào)查道路的損毀情況，但直到現(xiàn)在幾乎沒(méi)有消息傳回。
幸運(yùn)的是，此前T國(guó)政府調(diào)查過(guò)每條道路的強(qiáng)度，現(xiàn)在他們希望只利用這些信息估計(jì)災(zāi)情。具體地，給定每條道路在洪水后仍能通行的概率，請(qǐng)計(jì)算仍能通行的道路恰有N-1條，且能聯(lián)通所有城市的概率。

Input

輸入的第一行包含整數(shù)N。
接下來(lái)N行，每行N個(gè)實(shí)數(shù)，第i+l行，列的數(shù)G[i][j]表示城市i與j之
間仍有道路聯(lián)通的概率。
輸入保證G[i][j]=G[j][i]，且G[i][j]=0；G[i][j]至多包含兩位小數(shù)。

Output

輸出一個(gè)任意位數(shù)的實(shí)數(shù)表示答案。
你的答案與標(biāo)準(zhǔn)答案相對(duì)誤差不超過(guò)10^(-4)即視為正確。

Sample Input

3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0

Sample Output

0.375

HINT

1 < N < =50

數(shù)據(jù)保證答案非零時(shí)，答案不小于10^-4

Solution

題目即讓求：（$T$是生成樹(shù)，$e$是邊）
$\sum_{T}\prod_{e\in T} p_e \prod_{e\notin T}(1-p_e)$
把第二個(gè)$\prod$變一下
$\sum_{T}\prod_{e\in T} p_e \frac{\prod_{e}(1-p_e)}{\prod_{e\in T}(1-p_e)}$
也就是
$\prod_{e}(1-p_e)\sum_{T}\prod_{e\in T} \frac{p_e}{1-p_e}$。
其中行和矩陣$-$邊權(quán)矩陣的行列式的值$=\sum_{T}\prod_{e\in T} w_e$，其中$w$是邊權(quán)。
然后就可以高斯消元求解了。

Code

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #define N (59) 6 #define eps (1e-10) 7 using namespace std; 8 9 int n; 10 double a[N][N],f[N][N],ans=1; 11 12 void Gauss() 13 { 14 int w=1; 15 for (int i=1; i<=n-1; ++i) 16 { 17 int num=i; 18 for (int j=i+1; j<=n-1; ++j) 19 if (fabs(f[j][i])>fabs(f[num][i])) num=j; 20 if (num!=i) swap(f[num],f[i]), w=-w; 21 for (int j=i+1; j<=n-1; ++j) 22 { 23 double t=f[j][i]/f[i][i]; 24 for (int k=i; k<=n-1; ++k) 25 f[j][k]-=t*f[i][k]; 26 } 27 } 28 for (int i=1; i<=n-1; ++i) ans*=f[i][i]; 29 for (int i=1; i<=n; ++i) 30 for (int j=i+1; j<=n; ++j) 31 ans*=1-a[i][j]; 32 printf("%.10lf\n",ans*w); 33 } 34 35 int main() 36 { 37 scanf("%d",&n); 38 for (int i=1; i<=n; ++i) 39 for (int j=1; j<=n; ++j) 40 { 41 scanf("%lf",&a[i][j]); 42 if (a[i][j]==1) a[i][j]-=eps; 43 if (i==j) continue; 44 f[i][j]=-a[i][j]/(1-a[i][j]); 45 f[i][i]-=f[i][j]; 46 } 47 Gauss(); 48 }

轉(zhuǎn)載于:https://www.cnblogs.com/refun/p/10375388.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3534:[SDOI2014]重建(矩阵树定理)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。