傳送門
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！
轉載于:https://www.cnblogs.com/PaperCloud/p/10214423.html