[bzoj3534] [Sdoi2014] reconstruction matrix tree theorem

Description

T has N cities and is connected by several two-way roads. There is at most one road between a pair of cities.
After a flood, some roads were damaged and impassable. Although some people have begun to investigate the damage to the road, up to now, little information has been returned.
Xinyun is that the government of state T has investigated the intensity of each road before, and now they hope to use this information only to estimate the disaster situation. Specifically, given the probability that each road can still pass after flood, please calculate the probability that there are only N-1 roads that can still pass and can connect all cities.

Input

The first line of input contains the integer N.
Next N rows, N real numbers in each row, row i+l, the number of columns G[i][j] represents the city I and j
There is still a probability of road connectivity between them.
The input guarantees that G[i][j]=G[j][i], and G[i][j]=0; G[i][j] contains at most two decimal places.

Output

Output a real number of any number of digits to indicate the answer.
If the relative error between your answer and the standard answer does not exceed 10 ^ (- 4), it will be deemed as correct.

Sample Input

3

0 0.5 0.5

0.5 0 0.5

0.5 0.5 0

Sample Output

0.375

HINT

1 < N < =50

When the data guarantee answer is not zero, the answer shall not be less than 10 ^ - 4

Title Solution
https://www.cnblogs.com/Troywar/p/8183916.html

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
#define mod 1000000007
#define eps (1e-10)
using namespace std;
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*10+ch-'0';ch=getchar();}
    return x*f;
}
double tmp=1;
int n;
double a[105][105];
double det(int n)
{
    double ans=1.0;
    for (int i=1;i<=n;i++)
    {
        int k=i;
        for (int j=i+1;j<=n;j++) if (fabs(a[k][i])<fabs(a[j][i])) k=j;
        if (fabs(a[k][i])<eps) return 0.0;
        if (k!=i)
        {
            for (int j=i;j<=n;j++) swap(a[i][j],a[k][j]);
            ans=-ans;
        }
        for (int j=i+1;j<=n;j++)
        {
            double t=a[j][i]/a[i][i];
            for (int k=i;k<=n;k++)
                a[j][k]-=a[i][k]*t;
        }
        ans*=a[i][i];
    }
    return ans;
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            scanf("%lf",&a[i][j]);
            if(i==j) continue;
            if(a[i][j]+eps>1.0) a[i][j]-=eps;
            if(i<j) tmp*=1-a[i][j];
            a[i][j]/=1-a[i][j];
        }
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(i!=j) a[i][i]+=a[i][j],a[i][j]=-a[i][j];
    double ans=det(n-1)*tmp;
    printf("%.10lf",ans);
    return 0;
}

Tags: less

Posted on Sun, 03 May 2020 05:13:08 -0700 by seansd