牛客网 给定一个n,求 n 个节点的树的最大团个数的期望。 最大团的定义是选出最多的点,使得任意两点之间都有边.c++代码
时间: 2024-02-28 08:55:54 浏览: 17
这道题可以通过容斥原理来解决。首先,我们可以求出不考虑任何边的情况下,最大团的个数期望为1,即每个点都独立成为一个最大团的概率为1/n。接着,我们考虑有一条边连接的两个点x和y,它们不在同一个最大团中的概率为(1-1/(2^(size(x)+size(y)-2))),其中size(x)表示以点x为根的子树大小。因此,它们至少在一个最大团中的概率为1-(1-1/(2^(size(x)+size(y)-2)))=1/2^(size(x)+size(y)-2)。因此,我们可以得到最大团的个数期望为:
E = 1 - Σ[size(x)+size(y)-2≤n] 1/2^(size(x)+size(y)-2)
其中,Σ[size(x)+size(y)-2≤n]表示求和的范围为所有满足size(x)+size(y)-2≤n的点对(x,y)。这个式子可以用类似于 Floyd 算法的方式来计算,时间复杂度为O(n^3)。以下是代码实现:
```c++
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1005;
double dp[MAXN][MAXN];
int n;
int main() {
scanf("%d", &n);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = 1;
for (int k = i; k < j; k++) {
dp[i][j] += dp[i][k] * dp[k+1][j] / (1 - 1.0 / (1 << (j - i)));
}
}
}
double ans = 0;
for (int i = 1; i <= n; i++) ans += dp[1][i];
printf("%.10lf\n", ans);
return 0;
}
```