联动：https://pst.iorinn.moe/archives/matrix-tree.html

Problem

https://www.luogu.org/problemnew/show/P3317

Solution

加深了对 Matrix-tree 的理解。

Matrix-tree 求解的实际上是这个式子：
$$\sum_{tree} \prod_{(u,v)\in E} W_{(u,v)}$$

而对角线上的也不是度数，而是所连边权的和...

具体的式子推导可以看这里：https://stone41123.blog.luogu.org/solution-p3317

同时如果某边概率接近 1.0，我们需要一个近似 1.0 的值才能进行 gauss 求解，否则会 nan。

同时只是为了求得上三角行列式，可以用 gauss-jordan 消元法。

以及因为矩阵元素全部取反了所以最后取个 abs...

同时 matrix-tree 的性质可以让我们无视交换两行行列式变相反数的性质...

Code

// Code by ajcxsu
// Problem: rebuild

#include<bits/stdc++.h>
#define eps (1e-8)
using namespace std;

const int N=51;
long double mat[N][N];

long double gauss(int n) {
    int u;
    long double ret=1.0;
    for(int i=1;i<n;i++) {
        u=i;
        for(int j=i+1;j<n;j++) if(fabs(mat[u][i])<fabs(mat[j][i])) u=j;
        if(u!=i) swap(mat[u], mat[i]);
        if(fabs(mat[i][i])<eps) return 0.0;
        for(int j=i+1;j<n;j++) mat[i][j]/=mat[i][i];
        ret*=mat[i][i];
        for(int j=i+1;j<n;j++)
            if(j!=i)
                for(int k=i+1;k<n;k++) mat[j][k]-=mat[j][i]*mat[i][k];
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout.setf(ios::fixed), cout<<setprecision(5);
    int n;
    cin>>n;
    long double tmp=1.0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) {
         cin>>mat[i][j];
         if(1.0-mat[i][j]<eps) mat[i][j]=1-eps; // 0w0
         if(i<j) tmp*=1.0-mat[i][j];
         mat[i][j]/=1.0-mat[i][j];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j) mat[i][i]-=mat[i][j];
    cout<<fabs(gauss(n)*tmp)<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3317.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆