题目大意
T国有$N$个城市，用若干双向道路连接。一对城市之间至多存在一条道路。
在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。
幸运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有$n-1$条，且能联通所有城市的概率。
题目分析
考虑对于一个生成树，其出现概率为 所选边出现概率的积 乘以 未选边不出现概率的积。
即：
通过基尔霍夫矩阵记录边权，可以算出生成树边权的积的和，其值即为行列式。
这正是我们要求的，因此高斯消元求行列式即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=55;
const double eps=1e-8;
int n;
double a[maxn][maxn],ans=1;
void Gauss() {
for(int i=1; i<=n; i++) {
int row=i;
for(; row<=n; row++)if(fabs(a[row][i])>eps)break;
if(row>n)continue;
if(row!=i) {
for(int j=1; j<=n; j++)swap(a[i][j],a[row][j]);
ans*=-1;
}
for(int j=i+1; j<=n; j++) {
double t=a[j][i]/a[i][i];
for(int k=i; k<=n; k++)a[j][k]-=t*a[i][k];
}
ans*=a[i][i];
}
}
int main() {
n=Get_Int();
double tmp=1;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
scanf("%lf",&a[i][j]);
if(i==j)continue;
if(i<j)tmp*=1-a[i][j];
a[i][j]/=1-a[i][j];
}
n--;
for(int i=1; i<=n+1; i++)
for(int j=1; j<=n+1; j++)
if(i!=j)a[i][i]+=a[i][j],a[i][j]=-a[i][j];
Gauss();
printf("%0.10lf\n",tmp*ans);
return 0;
}
|
