BZOJ 3534: [Sdoi2014]重建(Matrix Tree)

传送门

解题思路

　　比较容易看的出来矩阵树定理。然后就怒送一Wa，这个矩阵树定理是不能直接用的。题目要求的其实是这个玩意。

\[ans=\sum\limits_{Tree}( \prod\limits_{e\in Tree}p_e*\prod\limits_{e\notin Tree}(1-p_e))
\]

而矩阵树能求的东西本质上其实是每棵生成树的积的和，说人话就是这个。

\[now=\sum\limits_{Tree}\prod\limits_{e\in Tree}w_e
\]

这个形式跟上面那个很像，但还是有点不一样。我们考虑将上面那个式子化简。根据

\[\prod\limits_{e\notin Tree}(1-p_e)=\frac{\prod\limits_e (1-p_e)}{\prod\limits_{e\in Tree}(1-p_e)}
\]

把这玩意往最上面那个式子里一带，神奇的事情发生了：

\[ans=\prod\limits_e(1-p_e)*\sum\limits_{Tree} \frac{\prod\limits_{e\in Tree}p_e}{\prod\limits_{e\in Tree}(1-p_e)}
\]

前面这个玩意可以直接算出来。后头这个玩意直接上矩阵树，把邻接矩阵的边权改成\(\frac{p_e}{1-p_e}\)就行了。

通过这道题，让我们明白了原来矩阵树里的那个边权是可以自己规定的，算出来的结果为每个生成树的积之和。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const int MAXN = 55;

const double eps = 1e-8;

int n;

double ans=1.0,base=1.0,f[MAXN][MAXN];

inline void Matrix_tree(){

	double t;int p;

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

		p=i;

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

			if(fabs(f[p][i])<fabs(f[j][i])) p=j;

		if(p!=i) swap(f[i],f[p]);

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

			t=f[j][i]/f[i][i];

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

				f[j][k]-=t*f[i][k];

		}

		ans*=f[i][i];

	}

}

int main(){

	scanf("%d",&n);

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

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

			scanf("%lf",&f[i][j]);if(i==j) continue;

			if(f[i][j]>1.0-eps) f[i][j]-=eps;

			if(i>j && f[i][j]>eps) base*=(1-f[i][j]);

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

		}

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

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

			f[i][i]+=f[i][j],f[i][j]=-f[i][j];

	Matrix_tree();printf("%.10lf",ans*base);

	return 0;

}

巴特西

BZOJ 3534: [Sdoi2014]重建(Matrix Tree)

解题思路

最新文章

热门文章