给出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 }