题解 P3343 【[ZJOI2015]地震后的幻想乡】

· · 题解

期望神题…… 这道题和今年NOIPD2T2极度神似，不知道NOIP2018要毒瘤到哪里去了

我们首先见到这道题，第一反应是——不会

所以我们要写暴力。

其实，如果知道边的排名的话，跑kruskal就好了对吧

但是我们不知道排名

所以暴力枚举边的全排列，跑kruskal，用题目中给的结论更新答案即可

复杂度n*m!

显然太暴力了，但是如果你记得NOIP2017D2T2的话，会发现它也有一个类似的全排列枚举+贪心的做法

然后优化呢？

子集DP，是子集DP，全排列之所以复杂度高，是因为它给了我们许多不需要的信息，对于这道题，我们只需两个信息，一是状态，二是联通性 从而把期望问题转化为计数问题

那么这个是可以状压的，当然，你会发现设f[s][i]表示点集s全部联通,最大边排名为i是不可转移的

所以这里有个操作叫正难则反

我们设dp[k][i][s](k为0/1变量)(s为二进制串)为加入前i条边时 点集s联通/不连通的概率。

先解释一下为什么变成了前i条边，因为这里要求的代价是最大边最小，而不是总和最小，所以平常做kruskal中被“跳过”的边，此时是无需付出代价的，所以也可以记为一种方案

转移的话，我们可以枚举其中的一个顶点，哪一个无所谓，只是在求dp[0][s][i]的时候这个点p要不变，枚举s的子集，该子集必须包含p

那么dp[0][s][i]=sigma(dp[1][s'][j]*c[i-j][size[s^s']]) 其中size为一个点集中边的数目

那么，这是什么意思呢？，相当于我们依照点p将这个集合剖为两半了 而我们是在枚举这个不联通集合联通块的大小

由于s^s'只能在本身内部连边，所以，s^s'一定和s'不联通，所以s一定不连通，而且因为枚举所有的“分割线”所以不重不漏的枚举了所有方案

另一个性质dp[0][i][j]+dp[1][i][j]=c[i][size[j]]

这个东西应该是显然？好吧还是解释下：因为已经把问题转化为了一个边可以全取问题，也就是说已经不是树了，因此边可以想怎么取就怎么取，除了联通不联通就没有了别的限制，因此dp[0]与dp[1]覆盖了所有的组合数

那么我们就可以愉快的递推了，这里有一个操作是枚举子集的，如果要枚举s的子集，那么可以用这样的语句：

for(int k=(s-1)&s;k>0;k=(k-1)&s);

就可以愉快的枚举子集了

最后，是如何生成答案，很遗憾，答案并不能由dp[1]得到，为什么？ 因为把原问题反了一下，我们求出来的是成功联通的方案，而不是什么 最小生成树，想必联通图和树之间的差别还是极大的

那么为了得出答案，我们可能也要反一下原问题，想一下，现在尽管是无条件加边，但是如果在加第X条边的时候刚好联通了，这时的联通图，对应的最小生成树最大边也是x.

也是说，连到第X条边时刚好联通的联通图，与最大边为X的最小生成树，一一对应

那么我们现在要求最大边的期望：

1.设最大边一种可能的排名取值为xi

2.设某一取值xi出现的概率为P(xi)

3.设x的取值不比x0小的概率为p(x>=x0)

4.设点集的全集为U

那么最大边的排名的期望就是：

sigma(xi*p(xi)) [i∈(1~m)]

对上述式子求一个前缀和，上式等价于(不能理解就记成结论好咯)

sigma(p(x>=i))[i∈(1~m)]

反一下，等价于

sigma(dp[0][i][U]/c[i][m]) [i∈(0~m)]

ok，毕竟取到i不连通的概率是等价于最大边大于i概率的

这样就求出了边排名的期望，除个m+1就行了

上代码~

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll dp[2][60][2200];ll size[2200];bool book[2200];
int n;int m;ll c[60][60];int up;
int map[20][20];double res;
int main()
{
    scanf("%d%d",&n,&m);up=pow(2,n)-1;
    for(int i=1;i<=m;i++)
    {
        int u;int v;
        scanf("%d%d",&u,&v);
        map[u-1][v-1]=1;map[v-1][u-1]=1;//用邻接矩阵存 
    }
    for(int i=1;i<=up;i++)
    {
        for(int p1=1;p1<n;p1++)
        {
            for(int p2=0;p2<p1;p2++)
            {
                size[i]+=((i>>p1)&1)&&((i>>p2)&1)&&map[p1][p2];//暴力计算size 
            }
        }
    }
    c[0][0]=1;
    for(int j=1;j<=m+1;j++)//递推杨辉三角 
    {
        c[0][j]=1;
        for(int i=1;i<j;i++)
        {
            c[i][j]=c[i][j-1]+c[i-1][j-1];
        }
        c[j][j]=1;
    }
    for(int i=0;i<=up;i++){dp[0][0][i]=1;}
    for(int i=0;i<n;i++){dp[1][0][1<<i]=1;dp[0][0][1<<i]=0;}
    //边界条件,显然一个点是联通的 
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=up;j++)
        {
            int p1=0;for(;((j>>p1)&1)==0;p1++);//随便选一个剖分点 
            for(int k=(j-1)&j;k>0;k=(k-1)&j)//枚举子集 
            {
                if(((k>>p1)&1)==0)continue;//不包含就算了 
                for(int rk=0;rk<=i;rk++)//枚举补集可用的边数 
                {
                    dp[0][i][j]+=dp[1][rk][k]*c[i-rk][size[j^k]];
                }
            }
            dp[1][i][j]=c[i][size[j]]-dp[0][i][j];//同时求出dp[1] 
        }
    }
    for(int i=0;i<=m;i++){res+=(double)dp[0][i][up]/(double)(c[i][m]);}//处理出概率 
    printf("%lf",(double)res/(double)(m+1));return 0;//拜拜程序~ 
}