[bzoj 3534][Sdoi2014] 重建

传送门

Description

Solution

怎么求行列式？

讲得很浅显的博客

这里有几个性质：

• 交换两行（列），行列式变号
• 加上另外一行的\(k\)倍，行列式不变

所以用高斯消元，把它变成一个上三角矩阵，那么它的行列式就是对角线的乘积啦

Code 

#include <bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define abs(x) (x>0?x:-x)

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

}

#define eps (1e-8)

int n;

double ans=1.,a[55][55];

double Gauss()

{

    double ret=1.;

    register int i,j,k;

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

    {

        //for(j=i+1;j<n;++j)

        //    if(abs(a[j][i])>abs(a[i][i])) std::swap(a[j],a[i]),ret=-ret;

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

        {

            double t=a[j][i]/a[i][i];

            for(k=i;k<n;++k) a[j][k]-=t*a[i][k];

        }

        ret*=a[i][i];

    }

    return abs(ret);

}

int main()

{

    scanf("%d",&n);

    register int i,j;

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

	{

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

		double t=fabs(1.-a[i][j])<eps?eps:(1.-a[i][j]);

        if(i<j) ans*=t;

        a[i][j]=a[i][j]/t;

	}

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

        if(i!=j) a[i][i]+=a[i][j],a[i][j]=-a[i][j];

    printf("%.10lf\n",Gauss()*ans);

    return 0;

}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！