「SDOI2014」重建 - 基尔霍夫矩阵 | Bill Yang's Blog

「SDOI2014」重建 - 基尔霍夫矩阵

题目大意

    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;
}
姥爷们赏瓶冰阔落吧~
0%