题解 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的子集，那么可以用这样的语句： ```C 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就行了 上代码~ ```C #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;//拜拜程序~ } ```