[bzoj 3534][Sdoi2014] 重建

传送门

Description

 T国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。

在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。

幸运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。

Solution

给出每条边出现的概率，求生成一棵树的概率。

首先要知道矩阵树定理和变元矩阵树定理。。。

对于一个无向图G，它的生成树个数等于其基尔霍夫Kirchhoff矩阵任何一个N-1阶主子式的行列式的绝对值

基尔霍夫Kirchhoff矩阵 K =度数矩阵 D - 邻接矩阵 A

这里邻接矩阵可以有不同形式

• 如果\(A[i][j]\)表示i\(i\)和\(j\)之间边的数量，则\(det\)等于生成树的数量
• 如果\(A[i][j]\)表示\(i\)和\(j\)之间边的长度，则\(det=\sum_{T} \prod T_{e_i}\),也就是每个生成树的边权积之和

怎么求行列式？

讲得很浅显的博客

这里有几个性质：

• 交换两行（列），行列式变号
• 加上另外一行的\(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！