「SDOI2014」重建

题意

给一个图\(G\)，两点\((u,v)\)有边的概率是\(p_{u,v}\)，求有\(n-1\)条边通行且组成了一颗树的概率是多少。

抄了几个矩阵树定理有趣的感性说法

• 矩阵树定理的度数矩阵记录的是每个点的边权和，邻接矩阵记录的是边权，求的则是所有生成树的边权乘积和

• 考虑Kirchhoff矩阵的意义：\(K[G]=D[G]?A[G]=B[G]B^T[G]\)，之所以能够进行生成树计数是对于其伴随矩阵在计数\(n?1\)条边的集合时，当\(n?1\)条边中存在环就会产生线性组合而导致行列式为零，否则恰好对角线上均为伴随矩阵中所赋的值，使得\(\det(B_{i,j})^2\)就为\(1\)

考虑直接把度数矩阵赋为出度概率和，连边矩阵为概率，然后相减套矩阵树定理求得是什么
\[ \sum_T\prod_{(u,v)\in T}p_{u,v} \]
然而我们需要求
\[ \sum_T\prod_{(u,v)\in T}p_{u,v}\prod_{(u,v)\notin T}(1-p_{u,v}) \]
化一下可以得到
\[ \prod_{(u,v)\in G}(1-p_{u,v})\sum_T\prod_{(u,v)\in T}\frac{p_{u,v}}{1-p_{u,v}} \]
然后把后面的拿去跑矩阵树就可以了。

注意一些精度问题，把\(p=0\)搞成\(p=\epsilon\)，\(p=1\)搞成\(1-\epsilon\)差不多就可以了

Code:

#include <cstdio>
#include <cmath>
#include <algorithm>
const int N=52;
const double eps=1e-10;
int n;
double p[N][N],a[N][N];
void Gauss()
{
    --n;
    for(int i=1;i<=n;i++)
    {
        int id=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(a[id][i])<fabs(a[j][i])) id=j;
        std::swap(a[id],a[i]);
        for(int j=i+1;j<=n;j++)
        {
            double p=a[j][i]/a[i][i];
            for(int k=n;k>=i;k--)
                a[j][k]-=a[i][k]*p;
        }
    }
}
int main()
{
    scanf("%d",&n);
    double sum=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%lf",&p[i][j]);
            if(p[i][j]==0) p[i][j]=eps;
            if(p[i][j]==1) p[i][j]=1-eps;
            if(i<j) sum*=1-p[i][j];
            a[i][j]=p[i][j]/(1-p[i][j]);
        }
    for(int i=1;i<=n;i++)
    {
        a[i][i]=0;
        for(int j=1;j<=n;j++)
            if(i!=j)
                a[i][i]+=a[i][j],a[i][j]=-a[i][j];
    }
    Gauss();
    for(int i=1;i<=n;i++) sum*=fabs(a[i][i]);
    printf("%.4lf\n",sum);
    return 0;
}

2019.2.21

「SDOI2014」重建 解题报告

原文：https://www.cnblogs.com/butterflydew/p/10415092.html