原来矩阵树定理对于边是概率的情况也是适用的qwqwq。
ref
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
double w[55][55], uu;
const double eps=1e-7;
void gauss(){
for(int i=1; i<=n; i++){
int maxi=i;
for(int j=i+1; j<=n; j++)
if(fabs(w[j][i])>fabs(w[maxi][i]))
maxi = j;
swap(w[maxi], w[i]);
for(int j=i+1; j<=n; j++){
double blv=w[j][i]/w[i][i];
for(int k=i; k<=n; k++)
w[j][k] -= blv * w[i][k];
}
}
}
int main(){
cin>>n;
double tmp=1.0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++){
scanf("%lf", &uu);
if(i!=j){
if(uu>=1-eps) uu = 1 - eps;
if(uu<eps) uu = eps;
if(i<j) tmp *= 1 - uu;
w[i][j] = uu / (1 - uu);
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i!=j){
w[i][i] += w[i][j];
w[i][j] *= -1;
}
n--;
gauss();
for(int i=1; i<=n; i++)
tmp *= w[i][i];
if(tmp<0) tmp *= -1;
printf("%.12f
", tmp);
return 0;
}