Luogu

分析

显然答案为
$$
\sum_{T}\prod\limits_{e\in T}p_e\prod\limits_{e\not\in T}(1-p_e)
$$
考虑到
$$
\prod_{e\not\in T}(1-p_e)=\frac{\prod_e(1-p_e)}{\prod_{e\in T}(1-p_e)}
$$
代回去得到答案为
$$
\prod\limits_{e}(1-p_e)\sum\limits_{T}\prod\limits_{e\in T}\frac{p_e}{1-p_e}
$$
我们知道矩阵树定理求的实际上是 $\sum_T \prod_{e \in T} w_e$，于是我们可以使用矩阵树定理算出后面东西。

但是有 $p_e = 1$ 的情况，我们只需要把 $p_e$ 设为 $1-\epsilon $ 即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=50+10;
const double EPS=1e-8;

int n;
double G[N][N],prod=1.0;

inline double calc() {
    for (re int i=1;i<n;++i) {
        int pos=i;
        for (re int j=i+1;j<n;++j)
            if (fabs(G[j][i])>fabs(G[pos][i])) pos=j;
        swap(G[pos],G[i]);
        for (re int j=i+1;j<n;++j) {
            double t=G[j][i]/G[i][i];
            for (re int k=i;k<n;++k) G[j][k]-=t*G[i][k];
        }
    }
    double ans=1.0;
    for (re int i=1;i<n;++i) ans*=G[i][i];
    return ans;
}

int main() {
    scanf("%d",&n);
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            scanf("%lf",&G[i][j]);
            if (i==j) continue;
            if (1-G[i][j]<EPS) G[i][j]=1-EPS;
            if (i<j) prod*=(1-G[i][j]);
            G[i][j]/=(1-G[i][j]);
        }
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            if (i!=j) G[i][i]+=G[i][j],G[i][j]=-G[i][j];
    printf("%.10lf\n",prod*calc());
    return 0;
}