【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 ;
}
上一篇:ABP框架实战 1.基础信息维护


下一篇:robotframework笔记8