AtCoder Beginner Contest 187 F - Close Group

[Wizmann]

题意

给你一个无向图，N个点M条边。

问最少能有多少个团。

团（clique）：一个无向图，所有点之间两两之间都有边。（一个点视做团）

• 1 <= N <= 18

解法

先用O(n * 2^n)的暴力枚举出图中所有的团。

然后依次用二进制枚举所有的子图。

• 一个子图如果是团，则组成子图的团数为1
• 一个子图可以由两个子图A、B构成。A和B分别由一个或多个团构成。组成当前子图的团数 = 组成子图A的团数 + 组成子图B的团数。

问题：枚举子图的子图，会引入额外的复杂度，使得题目最终的时间复杂度为O(2^N * 2^N)。

需要使用以下方法进行枚举：

    for (int i = 1; i < (1 << n); i++) {
        for (int j = i; j != 0; j = (j - 1) & i) {
            dp[i] = min(dp[i], dp[j] + dp[i ^ j]);
        }
    }

理论依据：需要枚举的所有状态数上限为O(3^N)，因为一个点至多有3个状态：在子图A中、在子图B中，不在任何一个子图中。所以，以上枚举所需要的复杂度为O(3^N） 题目 Code 参考