【Luogu】P3317重建（高斯消元+矩阵树定理）

　　题目链接

　　因为这个专门跑去学了矩阵树定理和高斯消元qwq

　　不过不是很懂。所以这里只放题解

　　玫葵之蝶的题解

　　某未知dalao的矩阵树定理

　　代码

#include<cstdio>

#include<cstdlib>

#include<cctype>

#include<algorithm>

#include<cstring>

#include<cmath>

#define eps 1e-8

#define maxn 100

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

double s[maxn][maxn];

int main(){

    int n=read();

    double tmp=;

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

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

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

            if(fabs(s[i][j])<eps)    s[i][j]=eps;

            if(fabs(-s[i][j])<eps)    s[i][j]=-eps;

            if(i<j)    tmp*=(1.0-s[i][j]);

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

        }

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

        s[i][i]=;

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

            if(i^j)    s[i][i]-=s[i][j];

    }

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

        int now=i;

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

            if(fabs(s[j][i])>fabs(s[now][i]))    now=j;

        if(now!=i)    swap(s[now],s[i]);

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

            double ret=s[j][i]/s[i][i];

            for(int k=i;k<n;++k)    s[j][k]-=s[i][k]*ret;

        }

    }

    double now=;

    for(int i=;i<n;++i)    now*=s[i][i];

    now=fabs(now)*tmp;

    printf("%.10lf",now);

    return ;

}