最大团 / 独立集

· · 题解

写了写发现 TLE 了，然后发现自己居然不会 O(2^{n/2}) 求团诶。不过其实也没啥特别的地方。

这里就只写最大团了，反正两者本质相同。

首先有一个 O(n2^{n/2}) 的算法：类似折半搜索的思路，将总集合分成两半 \mathbb S,\mathbb T。对 \mathbb S,\mathbb T 的每个子集分别求出它们是否是团。对 \mathbb S 的子集施高维前缀和求出 f(S\subseteq\mathbb S) 表示集合 S 包含的所有团的信息和（本题中为最大值 + 数量的二元组）。然后枚举 \mathbb T 中的所有团 T\in\mathbb T，找出左边能够与 T 拼起来组成团的点集合 S=\bigcap\limits_{u\in T}E_u（其中 E_u 为 u 的邻居），将 f(S) 与 T 的信息合并即可。容易发现这样是不重不漏的。

写出代码发现唯一瓶颈是求 f(S) 的部分，如果用高维前缀和的话怎样都是 O(n2^{n/2}) 的。尝试直接考虑 f(S) 的定义是集合 S 包含的所有团的信息和，那么取出 S 中的任意一点 u\in S，分类 u 是否包含在一个团中，我们有

f(S)=f(S-u)+\Big(f\big((S-u)\cap E_u\big)\cup \{u\}\Big)

这样直接递推 f 就好啦，其他部分不用变，复杂度 O(2^{n/2})。

顺带一提，有一个经典题目 qoj7514 Clique Challenge，可以使复杂度与 m 挂钩，这个其他题解有写，我就懒得写做法了。

upd：一个可爱的女孩子让我放个代码，那就放吧：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define mems(x, v) memset(x, v, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double wisdom;

int n, m, popc[1 << 25], to[1 << 25], lg[1 << 25]; pair <int, ll> f[1 << 25]; ll E[55]; bool e[55][55], g[1 << 25];
void solve() {
    int mid = n / 2;
    for (int i = 1; i <= n; i++) e[i][i] = true, E[i] = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (e[i][j]) E[i] |= (1ll << (j - 1));

    for (int S = 0; S < (1 << mid); S++) f[S] = {0, 0}, g[S] = false;
    f[0] = {0, 1};
    for (int S = 1; S < (1 << mid); S++) {
        pair <int, ll> A = f[S ^ (S & -S)], B = f[(S ^ (S & -S)) & E[lg[S & -S]]];
        B.first |= (S & -S);
        if (popc[B.first] > popc[A.first]) A = B; else if (popc[B.first] == popc[A.first]) A.second += B.second;
        f[S] = A;
    }
    g[0] = true;
    for (int S = 1; S < (1 << (n - mid)); S++) {
        g[S] = g[S ^ (S & -S)] && !(S & ~(E[lg[S & -S] + mid] >> mid));
    }

    ll ans = 0, state = 0, tot = 0;
    for (int T = 0; T < (1 << (n - mid)); T++) if (g[T]) {
        // for (int i = 1; i <= n - mid; i++) if (T >> (i - 1) & 1) S &= E[i + mid];
        int S; to[T] = S = (!T ? (1 << mid) - 1 : to[T ^ (T & -T)] & E[lg[T & -T] + mid]);

        ll pc = popc[f[S].first] + popc[T], me = f[S].first | ((ll)T << mid);
        if (pc > ans) ans = pc, state = me, tot = f[S].second;
        else if (pc == ans) tot += f[S].second;
    }
    cout << ans << ' ' << tot << '\n';
    for (int i = 1; i <= n; i++) if (state >> (i - 1) & 1) cout << i << ' ';
    cout << '\n';
}
int main() {
    cin >> n >> m;
    for (int i = 1; i < (1 << ((n + 1) / 2)); i++) popc[i] = popc[i ^ (i & -i)] + 1;
    for (int i = 0; i < 25; i++) lg[1 << i] = i + 1;

    while (m--) {int u, v; cin >> u >> v; e[u][v] = e[v][u] = true;}
    solve(); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) e[i][j] ^= 1; solve();
    return 0;
}