[SDOI2014]重建

题目

我们都知道矩阵树求得实际是

\[\sum_{T}\prod_{e\in T}w_e\]

现在有一个简单的问题，给定一张带权图，要求所有生成树边权积的和，这个怎么求

很简单我们还是构造两个矩阵\(A,B\)

对于图中的每一个点\(u\)，记\(d_u\)为和这个点相连的边权和，那么\(a_{u,u}=d_u\)

对于图中的每一条边\((u,v,w)\)，有\(b_{u,v}=b_{v,u}=w\)

我们设\(C=A-B\)，之后求出\(C\)的任意一个余子式的值就好了

现在回到这道题，我们要求的东西是

\[\sum_{T}\prod_{e\in T}w_e\prod_{e\notin T}1-w_e\]

我们只能对在生成树里的边求积，于是考虑选择一条边后的贡献

显然有一个\(w_e\)的贡献，同时在\(\prod_{e=1}^m1-w_e\)中有一个消去了一个\(1-w_e\)，产生了一个\(\frac{1}{1-w_e}\)的贡献

于是我们现在可以把柿子化成这样

\[\prod_{i=1}^m(1-w_i)\sum_{T}\prod_{e\in T}\frac{w_e}{1-w_e}\]

这样的话一旦不选择一条边，就能在前面的那个\(\prod_{i=1}^m(1-w_i)\) 里消去\(1-w_e\)的贡献，最后就只留下了不选的边

还有几个实现的时候需要注意的地方，就是一条边一定会出现的时候，我们得给这个概率减小一点，避免除以\(0\)的情况

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
const double eps=1e-10;
const int maxn=55;
int n;
double a[maxn][maxn],b[maxn][maxn];
inline int check(double a,double b) {if(a+eps>b&&a-eps<b) return 1;return 0;}
int main() {
    scanf("%d",&n);
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=n;j++) 
            scanf("%lf",&b[i][j]);
    double ans=1;
    for(re int i=1;i<=n;i++) 
        for(re int j=1;j<=n;j++) {
            if(i==j) continue;
            if(check(b[i][j],0)) continue;
            if(check(b[i][j],1)) b[i][j]-=eps;
            if(i<j) ans*=(1-b[i][j]);
            a[i][j]-=(b[i][j])/(1-b[i][j]);
            a[i][i]+=(b[i][j])/(1-b[i][j]);
        }
    int o=0;
    for(re int i=1;i<n;i++) {
        int p;
        for(p=i;p<n;++p) if(!check(a[p][i],0)) break;
        if(p!=i) std::swap(a[p],a[i]),o^=1;
        for(re int j=i+1;j<n;j++) {
            double t=a[j][i]/a[i][i];
            for(re int k=i;k<n;k++)
                a[j][k]-=a[i][k]*t;
        }
    }
    for(re int i=1;i<n;i++) ans*=a[i][i];
    if(o) printf("%.10lf\n",-1.0*ans);
        else printf("%.10lf\n",ans);
    return 0;
}

[SDOI2014]重建

原文：https://www.cnblogs.com/asuldb/p/10723697.html