题目描述
https://www.luogu.com.cn/problem/P3317
简要题意：给定一个完全图，每条边的权值表示这条边存在的概率，求存在的边恰好构成一棵生成树的概率
$n\le 50$
Solution
首先容易得到答案为 $\sum_{T\in Tree}(\prod_{w\in T}p_e\prod_{w\notin T}(1-p_e))=\prod 1-p_e\sum_{T\in Tree}\sum_{e\in T}\frac{p_e}{1-p_e}$
后面那个东西用矩阵树定理来求就行了，需要注意如果 $|1-p_e|<\epsilon$，为了精度，我们需要将 $p_e$ 减掉 $\epsilon$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
#include <iomanip>
#include <cmath>
#define maxn 310
#define ll long long
using namespace std;
const double eps = 1e-8;
double g[maxn][maxn];
double Gauss(int n) {
double res = 1;
for (int i = 1; i <= n; ++i) {
int pos = -1;
for (int j = i; j <= n; ++j)
if (fabs(g[j][i]) > fabs(g[pos][i])) pos = j;
if (pos == -1 || fabs(g[pos][i]) < eps) return 0; swap(g[i], g[pos]); res *= pos == i ? 1 : -1;
res *= g[i][i];
for (int j = i + 1; j <= n; ++j)
for (int k = n; k >= i; --k)
g[j][k] -= g[j][i] / g[i][i] * g[i][k];
} return res;
}
int n;
double a[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; double ans = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
if (a[i][j] > 1 - eps) a[i][j] -= eps;
if (i < j) ans *= 1 - a[i][j];
}
for (int i = 1; i <= n; ++i) {
double sum = 0;
for (int j = 1; j <= n; ++j) g[i][j] = -a[i][j] / (1 - a[i][j]), sum += a[i][j] / (1 - a[i][j]);
g[i][i] = sum;
} cout << fixed << setprecision(5) << ans * Gauss(n - 1) << "\n";
return 0;
}
|