bzoj3534 [Sdoi2014]重建

变形的$Martix-Tree$定理

发现我们要求的是$\prod_{i \in E}{p_{i}} * \prod_{i \notin E}{(1-p_{i})}$

然后呢? 矩阵树对重边也有效对吧。考虑带权图，发现建出来的矩阵的任何一个$n-1$阶主子式的行列式的值都是其所有生成树的边权之积的和

那么就可以搞了，考虑每一条边权为$\frac{p_{i}}{(1-p_{i})}$，最后再乘一个$\prod{(1-p_{i})}$即可

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define eps 1e-10

 #define N 55

 using namespace std;

 int n;

 double g[N][N],a[N][N],ans=,tmp=;

 void gauss(){

     n--;

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

         int bst=k;

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

             if(fabs(a[i][k])>fabs(a[bst][k]))bst=i;

         if(bst!=k){

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

                 swap(a[k][i],a[bst][i]);

             ans*=-;

         }

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

             double t=a[i][k]/a[k][k];

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

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

         }

         ans*=a[k][k];

     }

 }

 int main(){

     scanf("%d",&n);

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

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

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

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

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

             if(g[i][j]==)g[i][j]-=eps;

             tmp*=(-g[i][j]);

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

             a[i][i]+=g[i][j];a[j][j]+=g[i][j];

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

         }

     }

     gauss();

     printf("%0.10lf\n",ans*tmp);

     return ;

 }