重建 题解
重建
题目大意
给定一张无向图，第 \(i\) 条边存在的概率为 \(p_i\)，求这个无向图是一颗树的概率。
思路分析
所求即为：
\[\sum_{T}\Bigg(\prod_{e\in T}p_e\Bigg)\Bigg(\prod_{e\not \in T}(1-p_e)\Bigg)
\]
其中，\(T\) 是一个边集，当 \(T\) 中的边均存在时且其他边均不存在时，原图构成一颗树。
解释一下：枚举每一颗树，对每一颗树出现的概率求和，而一颗树出现当且仅当所有属于树的边均出现且所有不属于树的边均不出现。
发现这个东西长的很像矩阵树定理的形式，对比一下，矩阵树定理求的是
\[\sum_{T}\prod_{e\in T}w_e
\]
也就是图的所有生成树的边权之积的和。
考虑转化一下：
\[\begin{aligned}\sum_{T}\Bigg(\prod_{e\in T}p_e\Bigg)\Bigg(\prod_{e\not \in T}(1-p_e)\Bigg)&=\sum_{T}\Bigg(\prod_{e\in T}p_e\Bigg)\Bigg(\frac{\prod (1-p_e)}{\prod_{e\in T}(1-p_e)}\Bigg)\\&=\Bigg(\prod (1-p_e)\Bigg)\sum_{T}\Bigg(\prod_{e\in T}\frac{p_e}{1-p_e}\Bigg)\end{aligned}
\]
故只需要对于每条边，将边权设为 \(\frac{p_i}{1-p_i}\)，再用矩阵树定理跑一遍，最后乘上前面的那个积就可以了。
注意，可能存在 \(p_i=1\) 的情况，这时可以将边权微调，比如设为 \(1-\text{eps}\)，这样对结果的影响在可接受精度之内。
代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=55;
#define eps 1e-8
int n;
double a[N][N],w[N][N],prod=1;
double solve(){
double ans=1,f=1;
for(int i=2;i<=n;i++)
for(int j=i+1;j<=n;j++){
while(a[i][i]>eps){
double div=a[j][i]/a[i][i];
for(int k=2;k<=n;k++)
a[j][k]-=div*a[i][k];
swap(a[i],a[j]);f=-f;
}
swap(a[i],a[j]);f=-f;
}
for(int i=2;i<=n;i++) ans=ans*a[i][i];
return ans;
}
void add(int u,int v,double w){
a[u][u]+=w;a[v][v]+=w;
a[u][v]-=w;a[v][u]-=w;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%lf",&w[i][j]);
if(i<=j) continue;
if(w[i][j]>1-eps) w[i][j]=1-eps;//微调
prod*=1-w[i][j];
w[i][j]=w[i][j]/(1-w[i][j]);
add(i,j,w[i][j]);
}
printf("%.5lf\n",prod*solve());
return 0;
}