传送门
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
",Gauss()*ans);
return 0;
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！