ZJOI2015 地震后的幻想乡
我们其实只需要边的相对的发小关系，我们只要知道这个边是第几就可以了，因为如果知道它是第几就知道权值期望是$\frac i {m+1}$
所以我们考虑这样一个dp，$dp[S][i]$表示加入第$i$小的边权时$S$是联通的方案数。
由于一个显然的前缀和，我们知道答案其实就是
但是这个$dp$咋推呢？我们可以类似 HDU5552 的做法来推，一样是算联通图的数量，所以可以一样算不联通图的数量，考虑$f[S][i]$表示$S$加入$i$边后不联通图的方案数量。
不联通图的方案可以一样套用那个题的做法，考虑固定一个点，并且由这个点连出一个联通图，并且剩下的点自己连，和这个点的联通图没得关系。
由于最后连成的图肯定是包含这个点的，所以可以不重不漏统计所有方案。于是我们可以写出方程：
其中$T$是$S$的一个子集，并且固定的这个点在$T$里面，$d[S]$表示$S$点集在图里的边的数量。
而且$f$和$dp$明显是互补的，所以和为$\binom {d[S]} {i}$。
这题就做完啦。
但是想想组合数可不可能太大导致爆炸了呢？发现这题组合数最大也就$C_{50}^{10}$这个级别（其实更小），才$10^{11}$左右，很稳。
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
47
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
using namespace std;
#define int long long
#define MAXN 12
#define chkmn( a , b ) ( (a) > (b) ? (a) = (b) , 1 : 0 )
#define chkmx( a , b ) ( (a) < (b) ? (a) = (b) , 1 : 0 )
int n , m;
long long dp[MAXN * MAXN][1 << MAXN] , f[MAXN * MAXN][1 << MAXN] , d[1 << MAXN];
vector<int> G[MAXN];
long long C[51][51];
signed main() {
cin >> n >> m;
C[0][0] = 1;
for( int i = 1 ; i <= m ; ++ i ) {
C[i][0] = 1;
for( int j = 1 ; j <= i ; ++ j ) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
for( int i = 1 , u , v ; i <= m ; ++ i ) {
scanf("%lld%lld",&u,&v); G[u].push_back( v );
}
for( int i = 1 ; i < ( 1 << n ) ; ++ i)
for( int j = 1 ; j <= n ; ++ j ) if( i & ( 1 << j - 1 ) )
for( int v : G[j] ) if( i & ( 1 << v - 1 ) )
++ d[i];
for( int i = 1 ; i <= m ; ++ i ) dp[i][0] = 1;
for( int s = 1 ; s < ( 1 << n ) ; ++ s ) {
int ps = 0;
for( int j = 1 ; j <= n ; ++ j ) if( s & ( 1 << j - 1 ) ) ps = j;
for( int i = 0 ; i <= d[s] ; ++ i ) {
for( int t = ( s - 1 ) & s ; t != s ; t = ( t - 1 ) & s ) {
if( ~t & ( 1 << ps - 1 ) ) continue;
for( int j = 0 ; j <= min( d[t] , i ) ; ++ j ) {
f[i][s] += dp[j][t] * C[d[s ^ t]][i - j];
}
}
dp[i][s] = C[d[s]][i] - f[i][s];
}
}
double res = 0.0;
for( int i = 1 ; i <= m ; ++ i )
res += 1.0 * i / ( m + 1 ) * ( 1.0 * dp[i][(1<<n) - 1] / C[m][i] - 1.0 * dp[i-1][(1<<n)-1] / C[m][i - 1] );
printf("%.6lf",res);
}
|
