Description：

一个图，给出每条边存在的概率，问构成一棵生成树的概率。

$1\leqslant n\leqslant51$

Solution：

首先我们可以枚举树 $T$ ，他的概率为： $$ \begin{align} &\prod_{e_i\in T}p_i\times\prod_{e_i\notin T}(1-p_i)\\ =&\prod _{e_i}(1-p_i)\prod_{e_i\in T}\frac{p_i}{1-p_i} \end{align} $$ 后面那个显然可以用变元矩阵树定理做。

变元矩阵树定理的基尔霍夫矩阵为： $g[i][j]=val[i][j]$ ， $g[i][i]=-\sum_{j\ne i}g[i][j]$ 。

当 $p_i=1$ 时设 $p_i=1-eps$ ， $p_i=0$ 时 $p_i=eps$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 52

double ans = 1.0;

double g[MAXN][MAXN];

double eps = 1e-8;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			scanf("%lf",&g[i][j]);

			if(fabs(g[i][j]) < eps)g[i][j] = eps;

			if(fabs(1.0 - g[i][j]) < eps)g[i][j] = 1 - eps;

			if(i < j)ans = ans * (1 - g[i][j]);

			g[i][j] = g[i][j] / (1 - g[i][j]);

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			if(i == j)continue;

			g[i][i] -= g[i][j];

		}

	}

	for(int i = 1;i < n;++i)

	{

		for(int j = i + 1;j < n;++j)

		{

			if(fabs(g[j][i]) >= fabs(g[i][i]))

			{

				for(int l = i;l < n;++l)swap(g[i][l],g[j][l]);

			}

		}

		for(int j = i + 1;j < n;++j)

		{

			double ratio = g[j][i] / g[i][i];

			for(int l = i;l < n;++l)g[j][l] -= g[i][l] * ratio;

		}

		ans = ans * g[i][i];

	}

	printf("%.8lf\n",fabs(ans));

	return 0;

}