Luogu

BZOJ

分析

puts("nan")可在BZOJ上AC


很神仙的一道题目。

考虑暴力枚举每颗树,答案就是$\large\sum\limits_{T}\prod\limits_{e\in T}p_e\prod\limits_{e\not\in T}(1-p_e)$

直观上理解就是树边选中的概率乘上非树边不选中的概率加起来。

基尔霍夫矩阵的任一个代数余子式是所有生成树的边权积之和,也就是$\large\sum\limits_{T}\prod\limits_{e\in T}w_e$。发现和上面的式子长得很像。

考虑到$\Large\prod\limits_{e\not\in T}(1-p_e)=\frac{\prod_e(1-p_e)}{\prod_{e\in T}(1-p_e)}$,代回去得到$\large ans=\prod\limits_{e}(1-p_e)\sum\limits_{T}\prod\limits_{e\in T}\frac{p_e}{1-p_e}$

然后可以将$w_i$设成$\frac{p_e}{1-p_e}$,然后就可以高斯消元算出后面的东西,再乘上前面那一段就行了。

如果$p_e=1$怎么办?

将$p_e$设成$1-eps$就行了。

代码

//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;
}
最后修改:2019 年 09 月 24 日 10 : 15 PM