首页 > 代码库 > POJ 3156 - Interconnect (概率DP+hash)

POJ 3156 - Interconnect (概率DP+hash)

题意:给一个图,有些点之间已经连边,现在给每对点之间加边的概率是相同的,问使得整个图连通,加边条数的期望是多少。

 

此题可以用概率DP+并查集+hash来做。

用dp(i,j,k...)表示当前的每个联通分量的点数分别是i,j,k...(连通分量的个数不固定)时,加边的期望。

这样以dp(i,j,k)为例分析状态转移的过程,dp(i,j,k)=p1*dp(i,j,k)+p2*dp(i+j,k)+p3*dp(i,j+k)+p4*dp(j,i+k)+1。

终止条件是dp(n)=0,因为此时图一定联通,所以期望是0。

这个式子是怎么来的呢?

p1*dp(i,j,k)表示增加了一条边之后原来的联通分量没有改变时的情况,p1表示选中这样的无用边的概率;p2*dp(i+j,k)表示增加了一条连结i和j这两个联通分量的边,p2表示选中i和j之间的边的概率。最后的1表示增加了一条边。

这里我们要计算选边概率。

首先有n*(n-1)/2条边。

如果选中了不改变图的联通分量的边,此时说明每次加的边都属于一个连通分量,所以一共有sum{(cnt(i)*cnt(i)-1)/2}(cnt(i)表示该联通分量内有cnt(i)个点)种选择情况。

如果选中了某条边连结了某两个联通分量i、j,这个时候一共有cnt(i)*cnt(j)种情况。

计算概率只需要除以边的总数即可。

计算连通分量可以用并查集。

因为这个题只看图的连通情况不在乎具体是哪个点,因此可以对每个联通分量的点数排序,使得每个状态唯一,这样可以得到很多重叠的子问题,整个问题就可以用记忆化搜索完成了。

很明显问题的状态比较复杂,直接下手很难处理也容易超时,所以用hash处理状态压缩判重。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define MOD 100007
using namespace std;
int n,m;
struct State
{
    double val;
    int x[31];
    bool vis;
    State()
    {
        memset(x,0,sizeof(x));
        vis=false;
    }
    void clear()
    {
        memset(x,0,sizeof(x));
        vis=false;
    }
    void mysort()
    {
        sort(x,x+30);
    }
    int myhash() const
    {
        int res=0;
        for(int i=29,b=1; i>=0&&x[i]; --i)
        {
            res+=x[i]*b;
            res%=MOD;
            b*=30;
            b%=MOD;
        }
        return res;
    }
    bool operator ==(State &t)const
    {
        for(int i=0; i<30; ++i) if(x[i]!=t.x[i]) return false;
        return true;
    }
    bool operator !=(State &t) const
    {
        return !(*this==t);
    }
};
State has[MOD+5],st;
void inserthash(State &p)
{
    int v=p.myhash();
    while(has[v].vis)
        if(++v==MOD) v=0;
    has[v]=p;
    has[v].vis=true;
}
double gethash(State &p)
{
    int v=p.myhash();
    while(has[v].vis&&has[v]!=p)
        if(++v==MOD) v=0;
    return has[v]==p?has[v].val:-1;
}
int father[35];
int find(int p)
{
    return p==father[p]?p:(father[p]=find(father[p]));
}
void init()
{
    for(int i=1; i<=n; ++i) father[i]=i;
    st.clear();
}
double DP(State &s)
{
    if(s.myhash()==n) return 0;
    double v=gethash(s);
    if(v!=-1.0) return v;
    double q=0,sn=n*(n-1)/2.0;;
    for(int i=29; i>=0&&s.x[i]; --i)
        q+=s.x[i]*(s.x[i]-1)/2.0;
    double &res=s.val;
    res=1;
    for(int i=29; i>=0&&s.x[i]; --i)
        for(int j=i-1; j>=0&&s.x[j]; --j)
        {
            double p=s.x[i]*s.x[j]/sn;
            State t;
            for(int k=29; k>=0; --k)
                if(k!=i&&k!=j) t.x[k]=s.x[k];
                else if(k==i)  t.x[k]=s.x[i]+s.x[j];
                else t.x[k]=0;
            t.mysort();
            res+=p*DP(t);
        }
    res=res/(1-q/sn);
    inserthash(s);
    return res;
}
int cnt[35];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=0; i<m; ++i)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int fx=find(x),fy=find(y);
            if(fx!=fy) father[fx]=fy;
        }
        memset(cnt,0,sizeof(cnt));
        for(int i=1; i<=n; ++i)
            cnt[find(i)]++;
        for(int i=1; i<=n; ++i)
            st.x[i-1]=cnt[i];
        st.mysort();
        printf("%.6f\n",DP(st));
    }
    return 0;
}
View Code

 

学习了http://www.cnblogs.com/swm8023/archive/2012/09/21/2696593.html。