UVA 11600 Masud Rana

vjudge

怕不是个假题

题意是每次随机一个点,并且连边,然后走过去,求使得整张图联通的期望

显然可以把已经存在的联通块缩起来,然后考虑状压,设\(f_s\)表示现在联通的联通块集合为\(s\)到达终止状态的期望步数,转移枚举下一步到达的状态.然后记\(sum\)为\(s\)联通块集合的点数,\(a_i\)为联通块\(i\)的点数,经过化简可以得到这个方程\(dp_{s}=\frac{n-1}{n-sum}+\sum_{j\notin s}dp_{s\cap\{j\}}\times\frac{a_j}{n-sum}\),记忆化搜索即可

你以为复杂度是\(O(2^{30})\),其实是\(O(能过)\)哒!

#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double

using namespace std;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
unordered_map<int,db> f;
int n,m,tt,ff[35],a[35];
bool v[35];
vector<int> e[35];
void dfs(int x,int &s)
{
    v[x]=1,++s;
    vector<int>::iterator it;
    for(it=e[x].begin();it!=e[x].end();++it)
    {
        int y=*it;
        if(!v[y]) dfs(y,s);
    }
}
db dp(int s,int sm)
{
    if(f.count(s)) return f[s];
    db an=0;
    an=(db)(n-1)/(db)(n-sm);
    for(int j=1;j<=tt;++j)
        if(!(s>>(j-1)&1))
            an+=dp(s|1<<(j-1),sm+a[j])*(db)a[j]/(db)(n-sm);
    return f[s]=an;
}

int main()
{
    int T=rd();
    for(int id=1;id<=T;++id)
    {
        f.clear();
        n=rd(),m=rd();
        for(int i=1;i<=n;++i) e[i].clear(),v[i]=0;
        for(int i=1;i<=m;++i)
        {
            int x=rd(),y=rd();
            e[x].push_back(y),e[y].push_back(x);
        }
        tt=0;
        for(int i=1;i<=n;++i)
            if(!v[i])
            {
                a[++tt]=0;
                dfs(i,a[tt]);
            }
        f[(1<<tt)-1]=0;
        printf("Case %d: %.6lf\n",id,dp(1,a[1]));
    }
    return 0;
}

UVA 11600 Masud Rana

原文：https://www.cnblogs.com/smyjr/p/11386070.html