【BZOJ 3534】: [Sdoi2014]重建

题目大意：（略）

题解：

　　相对误差……我好方。

　　考虑答案应该为所有合法答案概率之和。对于一个合法的生成树，其出现概率应为所有选取边的概率出现的积 乘以 所有未选取边不出现概率的积。

　　即:

$\;\prod_{e\in tree} p_e\prod_{e\notin tree}1-p_e$

$=\prod_{e\in tree}\frac{p_e}{1-p_e}\prod_{e}1-p_e$

　　然后按照新边权列行列式即可。

代码：

1 #include "bits/stdc++.h"
 2 
 3 using namespace std;
 4 
 5 const double eps=1e-9;
 6 
 7 const int N=100;
 8 
 9 int n;
10 double a[N][N];
11 
12  double det(){
13     double res=1;
14     for(int i=0;i<=n;++i)
15         for(int j=0;j<=n;++j)
16             if(i!=j) a[i][i]+=a[i][j],a[i][j]=-a[i][j];
17     for(int i=0;i<n;++i){
18         int p=i;
19         for(int j=i+1;j<n;++j)  if(fabs(a[j][i])>fabs(a[p][i]))p=j;
20         if(fabs(a[p][i])<eps)   return 0.0;
21         if(p!=i)  {for(int j=i;j<n;++j)    swap(a[p][j],a[i][j]);res=-res;}
22         for(int j=i+1;j<n;++j){
23             double t=a[j][i]/a[i][i];
24             for(int k=i;k<n;++k)
25                 a[j][k]-=a[i][k]*t;
26         }
27         res*=a[i][i];
28     }
29     return res;
30 }
31 
32 int main(){
33     double ans,tmp=1;
34     scanf("%d",&n);
35     for(int i=0;i<n;++i){
36         for(int j=0;j<n;++j){
37             scanf("%lf",&a[i][j]);
38             if(i==j) continue;
39             if(a[i][j]+eps>1.0) a[i][j]-=eps;
40             if(i<j) tmp*=1-a[i][j];
41             a[i][j]/=1-a[i][j];
42         }
43     }
44     --n;
45     ans=det()*tmp;
46     printf("%.10f\n",ans);
47     
48 }      

转载于:https://www.cnblogs.com/Troywar/p/8183916.html