「PKUWC2018」随机算法

80 阅读 0 评论 53 点赞

我是靠谱客的博主义气黑裤，最近开发中收集的这篇文章主要介绍「PKUWC2018」随机算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

有一个n个点的无向图，随机生成一个长度为n的排列，有一个初始为空的集合，按照这个排列遍历，若当前点与当前集合构成独立集，则加入这个点，求最终得到该图最大独立集的概率。
数据范围： $n \leq 20, m \leq n * (n - 1) / 2$

题解：

考场：考虑状压DP，但发现朴素地做，使状态能表示独立集的点和排列的点，状态数总不可避免地达到 $n^{2} times 2^{n}$ ，转移 $O (n)$ ，只有50pts。
正解：因为要求的是最大独立集，故有关最大独立集的状态一定要记，考虑对于不在独立集内但在排列内的点，它们对转移没有影响，即转移时关心的只是每个点是否能被选为独立集内的点。于是记录该状态，再记一维独立集大小，计算方案数，转移时选取一个可选的点，对于这个点的影响，即新增的不可选的点，先乘上它在后面的排列的方案即可（这样做是因为以后就不考虑它们了，而它们也对以后没有影响），这样 $O(n^{2} times 2^{n})$ 。又发现对于一个确定的可选方案，它的最大独立集大小是确定的，且只有最大独立集的情况能对后面的产生影响，于是同时DP状态对应的最大独立集大小，可达到 $2^{n})$ 。