POJ 3156 Interconnect

现在有n个点，给你m条边，每次随机选2个点连边(可能选已经连过的)并且花费1个代价，求使n点联通的期望最小代价。

本题关心每个联通块的规模，但不关心每个联通块具体的点。
然后根据规模记忆化搜索，因为规模无法正常表示成值，所以每次hash一下当前dp的状态，然后记忆化搜索看是否已经算过并返回答案。

对于每个联通块，有两种情况，一种是和另一个联通块相连，第二种是和自己联通块内的点相连接。

设联通块x的规模为ax

对于第二种：每个联通块的连接概率是$(a[x])(a[x]-1)/(n(n+1))对于第一种情况：用两个for两两计算(a[i]a[j])2/(n(n-1))dp(nwe)其中nwe为将a[j]与a[i]相连后的状态

为了精度要求，可以先累加，最后除

由于式子为F=Fp1+Dp2$;所以要先把含F的移到另一边

最后返回答案即可

CODE：

#include <string.h>
#include <stdio.h>
#include <algorithm>
//贴了份题解，自己写了两遍，和题解对拍都没问题，但就是过不了
//欢迎大神指教
#define MAXN 50
#define INF 0x3f3f3f3f
#define MOD 100007
struct sta{
    int x[30],flag;
    double val;
    void clear() {memset(x, 0, sizeof x);}
    void sort() {std::sort(x, x + 30);}
    int hashme() {
        int v = 0;
        for (int i = 29, b = 1; i >= 1 && x[i]; i--)
            v += x[i] * b, v %= MOD, b *= 30, b %= MOD;
        return v;
    }
    bool operator ==(sta b) {
        for (int i = 0; i < 30; i++) if(x[i] != b.x[i]) return false;
        return true;
    }
    bool operator !=(sta b) {
        return *this == b ? false: true;
    }

}st,hh[MOD];
int n, m, tu, tv;
int p[MAXN], tot[MAXN];
int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}
void inshash(sta st) {
    int x = st.hashme();
    while (hh[x].flag == 1) {
        if (++x == MOD) x = 0;
    }
    hh[x] = st, hh[x].flag = 1;
}
double gethash(sta st) {
    int x = st.hashme();
    while (hh[x].flag == 1 && hh[x] != st) {
        if (++x == MOD) x = 0;
    }
    return hh[x] == st ? hh[x].val : -1;
}
double dp(sta ost) {
    if(ost.hashme() == n) return 0;
    double x = gethash(ost);
    if(x != -1.0)return x;
    //不会改变连通的方案
    double tmp = 0, ans = 0;
    for (int i = 0; i < 30; i++)
        tmp += (ost.x[i] * (ost.x[i] - 1)) /2;/// 2;
    //会把两个非连通子图连通的方案
    for (int i = 0; i < 30; i++) {
        for (int j = i+1; j < 30; j++) {
            if(ost.x[i]==0||ost.x[j]==0)continue;
            sta stt = ost;
            stt.x[i] += stt.x[j], stt.x[j] = 0;
            stt.sort();
            ans += ost.x[i] * ost.x[j] * dp(stt);
        }
    }

    ans /= (n * (n-1) / 2), ans++;
    ans /= (1 - tmp / (n * (n-1) / 2));
    ost.val = ans;
    inshash(ost);
    return ans;
}
int main(){
    scanf("%d%d", &n, &m);
        for (int i = 0; i < MOD; i++) hh[i].flag = 0;
        for (int i = 1; i <= n; i++) p[i] = i;
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &tu, &tv);
            p[find(tu)] = find(tv);
        }
        st.clear();
        int xs = 0;
        memset(tot, 0, sizeof tot);
        for (int i = 1; i <= n; i++) tot[find(i)]++;
        for (int i = 1; i <= n; i++) if(tot[i]) st.x[xs++] = tot[i];
        st.sort();
        printf("%.10f\n",dp(st));
    return 0;
}


/*
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#define mod 1999997
int n,m,fa[70],size[70];
inline int find(int x){
    return !fa[x]?x:fa[x]=find(fa[x]);
}
struct state {
    double val;
    int x[32],flag;
    void clear(){
        val=flag=0;
        memset(x,0,sizeof(x));
    }
    void sort(){
        std::sort(x+1,x+1+n);
    }
    int hash_get(){
        long long sum=0,base=1;
        for(int i=n;i&&x[i];--i){
            sum+=base*x[i];
            base*=30;
            base%=mod;sum%=mod;
        }
        return sum;
    }
    bool operator != (state m) {
        for(int i=n;i;--i){
            if(m.x[i]!=x[i]) return 1;
        }
        return 0;
    }
}hsh[mod];
inline double hash_find(state x){
    int sum=x.hash_get();
    while(hsh[sum].flag&&hsh[sum]!=x){
        ++sum;
        if(sum==mod) sum=0;
    }
    return hsh[sum]!=x?-1:hsh[sum].val;
}
inline double hash_add(state x){
    int sum=x.hash_get();
    while(hsh[sum].flag){
        ++sum;
        if(sum==mod) sum=0;
    }
    hsh[sum]=x;
    return hsh[sum].val;
}
inline int merge(int a,int b){
    int t1=find(a),t2=find(b);
    if(t1==t2) return 0;
    fa[t1]=t2;size[t2]+=size[t1];size[t1]=0;
    return 0;
}
double dp(state now){
    double x=hash_find(now);
    if(x!=-1) return x;
    if(now.hash_get()==n) return 0; 
    double self=0,other=0;
    for(int i=n;i&&now.x[i];--i){
        self+=now.x[i]*(now.x[i]-1)/2;
    }
    self/=(n*(n-1)/2);
    for(int i=n;i&&now.x[i];--i){
        for(int j=i-1;j&&now.x[j];--j){
            state nwe=now;
            nwe.x[i]+=nwe.x[j];nwe.x[j]=0;
            nwe.sort();
            other+=now.x[i]*now.x[j]*dp(nwe);
        }
    }
    other/=n*(n-1)/2;
    other+=1;
    other/=1-self;
    now.val=other;
    hash_add(now);
    return other;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i) size[i]=1;
    for(int i=1;i<=n;++i) hsh[i].clear();
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        merge(x,y);
    }
    int cnt=0;
    state start;start.clear();
    for(int i=1;i<=n;++i){
        if(size[i]) start.x[++cnt]=size[i];
    }
    start.sort();
    double ans=dp(start);
    printf("%.10lf\n",ans);
    return 0;
}
*/