ZigZagK

Never give up fighting!

[状压DP+组合]LOJ2540(PKUWC 2018)【随机算法】题解

题目概述

我们知道,求任意图的最大独立集是一类NP完全问题,目前还没有准确的多项式算法,但是有许多多项式复杂度的近似算法。

例如,小C常用的一种算法是:

  1. 对于一个 \(n\) 个点的无向图,先等概率随机一个 \(1..n\) 的排列 \(p[1..n]\)
  2. 维护答案集合 \(S\) ,一开始 \(S\) 为空集,之后按照 \(i=1..n\) 的顺序,检查 \(p[i]\cup S\) 是否是一个独立集,如果是的话就令 \(S=p[i]\cup S\)
  3. 最后得到一个独立集 \(S\) 作为答案。

小C现在想知道,对于给定的一张图,这个算法的正确率,输出答案对 \(998244353\) 取模。

解题报告

可以定义 \(f[i][s]\) 表示最大独立集大小为 \(i\) ,选的点状态为 \(s\) 的方案( \(0\) 没选 \(1\) 选了没用 \(2\) 用了),这样是 \(3\) 进制,不能承受。

然后我们发现一个点选了之后与其相连的点就不能选了,所以可以把这些点捆绑到该点上,这样就不用考虑选了没用的情况了,就变成了 \(2\) 进制了。具体可以Orz Lynstery

示例程序

点赞
  1. 访客Lynstery说道:

    %%%

     Google Chrome 66.0.3359.181   Windows 10
    回复
    1. 博主ZigZagK说道:
      @Lynstery

      全是看翰爷题解的Orz

       Google Chrome 66.0.3359.181   Linux
      回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]