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 
    
     #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
     
      abs(a[i][i])) std::swap(a[j],a[i]),ret=-ret;        for(j=i+1;j
     
    

---

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