给出N个点M条边，每次等概率的给这张图加一条边，求连通这个图加边次数的期望。
这题我们并不关心图的形状，只要知道图的连通情况即可，即这张图有几个连通块，每个连通块中有几个顶点。比如，我们用E(2,3,3)表示当这个图有3个连通块，每个连通块中的顶点数分别是2,3,3时，我们把它连通所需加边的期望，对于8个顶点的图，E(8)=0。可以得到转移方程
E(2,3,3)=p1*E(2,3,3)+p2*E(2,6)+p3*E(3,5)+1。
把右边的第一项移到左边，然后用记忆化搜索就可以求解了。
其中p1,p2,p3是转移到其它连通情况的概率，在8个点里连一条边，总的方案数显然是C(8,2)。如果这条边没有改变连通情况，说明连的是同一个连通块里的边，于是p1=(C(2,2)+C(3,2)+C(3,2))/C(8,2)。否则就是在两个连通块里各选了一条边，枚举可以得到p2=(3*3)/C(8,2)，p3=(2*3+2*3)/C(8,2)。
对图的每种状态先排个序，然后用HASH即可。
1 #include <string.h>
2 #include <stdio.h>
3 #include <algorithm>
4 #define MAXN 50
5 #define INF 0x3f3f3f3f
6 #define MOD 100007
7 struct sta{
8 int x[30],flag;
9 double val;
10 void clear() {memset(x, 0, sizeof x);}
11 void sort() {std::sort(x, x + 30);}
12 int hashme() {
13 int v = 0;
14 for (int i = 29, b = 1; i >= 1 && x[i]; i--)
15 v += x[i] * b, v %= MOD, b *= 30, b %= MOD;
16 return v;
17 }
18 bool operator ==(sta b) {
19 for (int i = 0; i < 30; i++) if(x[i] != b.x[i]) return false;
20 return true;
21 }
22 bool operator !=(sta b) {
23 return *this == b ? false: true;
24 }
25
26 }st,hh[MOD];
27 int n, m, tu, tv;
28 int p[MAXN], tot[MAXN];
29 int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}
30 void inshash(sta st) {
31 int x = st.hashme();
32 while (hh[x].flag == 1) {
33 if (++x == MOD) x = 0;
34 }
35 hh[x] = st, hh[x].flag = 1;
36 }
37 double gethash(sta st) {
38 int x = st.hashme();
39 while (hh[x].flag == 1 && hh[x] != st) {
40 if (++x == MOD) x = 0;
41 }
42 return hh[x] == st ? hh[x].val : -1;
43 }
44
45 double dp(sta ost) {
46 if(ost.hashme() == n) return 0;
47 double x = gethash(ost);
48 if(x != -1.0)return x;
49 //不会改变连通的方案
50 double tmp = 0, ans = 0;
51 for (int i = 0; i < 30; i++)
52 tmp += (ost.x[i] * (ost.x[i] - 1)) / 2;
53 //会把两个非连通子图连通的方案
54 for (int i = 0; i < 30; i++) {
55 for (int j = i+1; j < 30; j++) {
56 if(ost.x[i]==0||ost.x[j]==0)continue;
57 sta stt = ost;
58 stt.x[i] += stt.x[j], stt.x[j] = 0;
59 stt.sort();
60 ans += ost.x[i] * ost.x[j] * dp(stt);
61 }
62 }
63 ans /= (n * (n-1) / 2), ans++;
64 ans /= (1 - tmp / (n * (n-1) / 2));
65 ost.val = ans;
66 inshash(ost);
67 return ans;
68 }
69 int main(){
70 while (scanf("%d%d", &n, &m) != EOF) {
71 for (int i = 0; i < MOD; i++) hh[i].flag = 0;
72 for (int i = 1; i <= n; i++) p[i] = i;
73 for (int i = 0; i < m; i++) {
74 scanf("%d%d", &tu, &tv);
75 p[find(tu)] = find(tv);
76 }
77 st.clear();
78 int xs = 0;
79 memset(tot, 0, sizeof tot);
80 for (int i = 1; i <= n; i++) tot[find(i)]++;
81 for (int i = 1; i <= n; i++) if(tot[i]) st.x[xs++] = tot[i];
82 st.sort();
83 printf("%.10f\n",dp(st));
84 }
85 return 0;
86 }