题解：P12371 【模板】最大团/最大独立集

Missa · 2025-05-03 22:39:13 · 题解

一个比较好写的时空 O(2^{\frac{n}{2}}) 做法。

考虑每次去掉一个点搜索。我们希望记录一部分结果以减小复杂度，因此考虑每次去掉编号最大的那个点，并记忆化所有只使用编号最小的 n/2 个点的情况。

这里要记下的结果包含：大小，个数，和一个例子。只要能比较与合并一个点进去，就可以这样做。

下面考虑的是独立集（这样好写些）。

记当前集合为 S，要去掉的也是编号最大的点为 u，u 的领域为 E(u)。则，选 u 入独立集，转化在 S \backslash (E(U) \cup \{u\}) 上考虑原问题，并将 u 加入结果；否则，转化为在 S\backslash \{u\} 上考虑原问题。

考虑复杂度证明。前 n/2 步只会拓展出 2^{\frac{n}{2}} 个状态，而后 n/2 步涉及的总状态数不超过 2^{\frac{n}{2}}，由于记忆化每种只会被访问一次，因此这个做法的时空复杂度均为 2^{\frac{n}{2}}。

这个复杂度证明方式跟 CF1336E1 很像。

因为是独立集，要先对反图求解，再对原图求解。可以把开始的 E 就看成补集，但那样代码可读性会下降，我就没写。

#include <bits/stdc++.h>

using LL = long long;

struct node {
  int mx, cnt; LL ex;
  node(int mx = 0, int cnt = 1, LL ex = 0) : mx(mx), cnt(cnt), ex(ex) {}
  node operator + (const node &t) const {
    if (mx != t.mx) return mx > t.mx ? *this : t;
    return {mx, cnt + t.cnt, ex};
  }
  node operator + (int x) const {
    return {mx + 1, cnt, ex | (1ll << x)};
  }
};

int main() {
  int n, m; scanf("%d %d", &n, &m);
  std::vector<LL> e(n);
  for (int i = 0, u, v; i < m; i++) {
    scanf("%d %d", &u, &v), --u, --v;
    e[u] |= 1ll << v, e[v] |= 1ll << u;
  }
  LL lim = 1ll << (n / 2), all = (1ll << n) - 1;
  std::vector<node> f(lim);
  std::function<node(LL)> dfs = [&](LL st) {
    if (st < lim && f[st].mx > 0) return f[st];
    if (!st) return node();
    int x = std::__lg(st);
    LL r = st & (all ^ e[x] ^ (1ll << x));
    node ans = dfs(st ^ (1ll << x)) + (dfs(r) + x); 
    if (st < lim) f[st] = ans;
    return ans;
  };
  for (int i = 0; i < n; i++)
    e[i] = all ^ (1ll << i) ^ e[i];
  node ans = dfs(all);
  printf("%d %d\n", ans.mx, ans.cnt);
  for (int i = 0; i < n; i++) if (ans.ex & (1ll << i))
    printf("%d ", i + 1);
  printf("\n");
  for (int i = 0; i < n; i++)
    e[i] = all ^ (1ll << i) ^ e[i];
  f.assign(lim, node());
  ans = dfs(all);
  printf("%d %d\n", ans.mx, ans.cnt);
  for (int i = 0; i < n; i++) if (ans.ex & (1ll << i))
    printf("%d ", i + 1);
  printf("\n");
}