OI - 重建(洛谷) | Lucky_Glass's Blog
0%

OI - 重建(洛谷)

下半年也要继续努力啊


# 题意

> 洛谷P3317

点击展开/折叠题面

T国有 $N$ 个城市,用若干双向道路连接。一对城市之间至多存在一条道路。

在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到现在几乎没有消息传回。

幸运的是,此前 T 国政府调查过每条道路的强度,现在他们希望只利用这些信息估计灾情。具体地,给定每条道路在洪水后仍能通行的概率,请计算仍能通行的道路恰有 $N−1$ 条,且能联通所有城市的概率。


# 解析

形式化地表达一下我们要求的东西:

其中 T 是生成树。

我们发现,把 $p_i$ 作为边权,简单地套用 Matrix-Tree 定理,可以计算出 $\sum\limits_{T}\prod\limits_{i\in T}p_i$。考虑怎么补上后面的一个 Prod。

发现比较难直接统计在生成树外的乘积,但是我们可以间接地——在所有边权的乘积里除去在生成树里的边权的乘积。于是式子就变得非常简单了:

那么把 $\frac{p_i}{1-p_i}$ 作为边权,用Matrix-Tree跑就可以了。

但是有一个小细节,我们发现 $p_i=0$ 或 $p_i=1$ 时比较特殊。$p_i=0$ 时分子可能为 $0$,不过这不影响;$p_i=1$ 会让分母为 $0$,这影响就大了。$p_i=1$ 就是这条边一定会选,那么我们预先把这些必选的边连成的连通块缩点(用并查集),注意判断是否必选的边就已经有 circle 了。


# 源代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=55;
const double EPS=1e-7;

int n;
double mat[N][N],A[N][N];
int sot[N];

inline double ABS(const double &a){return a<0? -a:a;}
double Det(int siz){
double ret=1;
for(int i=1;i<siz;i++){
int it=-1;double tit=-1;
for(int j=i;j<siz;j++)
if(ABS(mat[j][i])>tit){
tit=ABS(mat[j][i]);
it=j;
}
if(tit<EPS) return 0;
if(it!=i){
for(int j=i;j<siz;j++) swap(mat[i][j],mat[it][j]);
ret=-ret;
}
ret*=mat[i][i];
for(int j=i+1;j<siz;j++){
if(ABS(mat[j][i])<EPS) continue;
double mul=mat[j][i]/mat[i][i];
for(int k=i;k<siz;k++) mat[j][k]-=mat[i][k]*mul;
}
}
return ret;
}
struct DSU{
int fa[N];
int FindFa(int u){return u==fa[u]? u:fa[u]=FindFa(fa[u]);}
bool Merge(int u,int v){
u=FindFa(u),v=FindFa(v);
if(u==v) return false;
fa[u]=v;
return true;
}
void Init(int siz){
for(int i=0;i<=siz;i++)
fa[i]=i;
}
}Ds;
int main(){
scanf("%d",&n);
Ds.Init(n);
double all=1;
bool ncir=true;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%lf",&A[i][j]);
if(i<j){
if(ABS(1-A[i][j])<EPS) ncir&=Ds.Merge(i,j);
else all*=(1-A[i][j]);
}
}
if(!ncir){
printf("0\n");
return 0;
}
int nsot=0;
for(int i=1;i<=n;i++){
int fai=Ds.FindFa(i);
if(!sot[fai]) sot[fai]=++nsot;
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
int u=sot[Ds.FindFa(i)],v=sot[Ds.FindFa(j)];
if(u==v) continue;
A[i][j]/=(1-A[i][j]);
mat[u][u]+=A[i][j];
mat[v][v]+=A[i][j];
mat[u][v]-=A[i][j];
mat[v][u]-=A[i][j];
}
printf("%.6f\n",Det(nsot)*all);
return 0;
}

THE END

Thanks for reading!