LibreOJ 3910 「PA 2022」Mędrcy

· · 题解

我的博客。

2024.07.02：修改了 T(k) 部分的错误。

考虑找一下走掉的条件:

  1. 若 x 第 1 天走掉，那么就说明 x 没有知道任何咒语。
  2. 若 x 第 2 天走掉，那么就说明应该存在一个 y，按照 x 已知的信息，y 应该没有掌握咒语，但是 y 第一天没走。
  3. 若 x 第 3 天走掉，那么就说明应该存在一个 (y, z)，按照 x 已知的信息应当不存在。
  4. 依次类推，若 x 第 c 天走掉，则说明存在 (a_1, a_2,\cdots, a_{c - 1})，按照 x 已知的信息应当不存在这种共同存在的情况。

转化一下，用 S_x 表示 x 会的咒语的集合。

  1. 若第 1 天走掉，那么说明 S_x = \varnothing。
  2. 若第 2 天走掉，那么说明存在 y 使得 S_x\cap S_y = \varnothing，即不存在 x, y 共存的咒语，x 就认为 y，x 就认为 y 没有掌握咒语。
  3. 若第 c 天走掉，那么说明存在 (a_1, a_2, \cdots, a_{c - 1})，S_x\cap S_{a_1}\cap S_{a_2}\cap \cdots \cap S_{a_{c - 1}} = \varnothing。

进一步的，考虑转化为补集的形式，令 T_x 表示 x 不会的咒语的集合。
那么第 c 天就走掉，那么说明存在 (a_1, a_2, \cdots, a_{c - 1})，T_x\cup T_{a_1}\cup T_{a_2}\cup \cdots \cap T_{a_{c - 1}} = \text{U}（\text{U} 指全集）。

然后因为又有每个咒语只有 2 个贤者没有掌握，考虑把咒语当作边，贤者当作点。
然后能发现要求的即是最小点覆盖和对应的方案。

这是经典 NPC 问题，但是能发现这里给了个特殊的 k\le 30。
这启发去试着弄一些优一点的东西。

考虑朴素的求解，即是遍历到一个点，并去抉择是否将其加入点集，然后递归下去，分为两种：

  1. 在点集里。
  2. 不在点集里，那么与其有连边的点都需要选。

考虑每次选剩余度数最大的点 u。

考虑复杂度，令 T(k) 为还能选 k 个点的复杂度。
其中第二种情况一种会选上 1 个点，一种会选上 \ge 3 个点（相邻的），所以有 T(k) = T(k - 1) + T(k - 3)，能得到 T(30) = 58425。

时间复杂度 \mathcal{O}(T(k)(n + m))。

注意判断重边，重边会使得度数实际上是假的。

#include<bits/stdc++.h>
const int maxn = 1e3 + 10;
int n, ed;
std::vector<int> to[maxn], P[maxn];
int deg[maxn];
int vis[maxn], ch[maxn], ans[maxn], ud[maxn], mn, now;
void dfsl(int u, int fa, int id) {
   if (ud[u]++) return ;
   P[id].push_back(u);
   for (int v : to[u])
      if (! vis[v] && v != fa)
         dfsl(v, u, id);
}
inline void del(int u, int val) {
   for (int v : to[u])
      deg[v] -= val;
}
void dfs() {
   if (now > mn) return ;
   int u = 0;
   for (int i = 1; i <= n; i++)
      if (! vis[i] && deg[i] > deg[u])
         u = i;
   if (! u) {
      if (now < mn)
         mn = now, memset(ans, 0, sizeof(int) * (n + 1));
      for (int i = 1; i <= n; i++)
         ans[i] |= ch[i];
   } else if (deg[u] > 2) {
      vis[u] = 1, del(u, 1);
      ch[u] = 1, now++;
      dfs();
      ch[u] = 0, now--;
      std::vector<int> V;
      for (int v : to[u]) 
         ! vis[v] && (V.push_back(v), del(v, 1), vis[v] = ch[v] = 1, now++);
      dfs();
      for (int v : V)
         vis[v] = ch[v] = 0, del(v, -1), now--;
      vis[u] = 0, del(u, -1);
   } else {
      memset(ud, 0, sizeof(int) * (n + 1));
      std::vector<std::pair<int, int> > tp;
      for (int i = 1; i <= n; i++)
         if (! vis[i] && ! ud[i] && deg[i] <= 1)
            P[i].clear(), dfsl(i, 0, i), tp.emplace_back(P[i].size() & 1, i);
      for (int i = 1; i <= n ;i++)
         if (! vis[i] && ! ud[i])
            P[i].clear(), dfsl(i, 0, i), tp.emplace_back(2, i);
      for (auto [op, p] : tp)
         now += P[p].size() + (op == 2) >> 1;
      if (now < mn)
         mn = now, memset(ans, 0, sizeof(int) * (n + 1));
      if (now == mn) {
         for (int i = 1; i <= n; i++)
            ans[i] |= ch[i];
         for (auto [op, p] : tp)
            if (op == 0 || op == 2) {
               for (int v : P[p])
                  ans[v] = 1;
            } else {
               for (int i = 1; i < P[p].size(); i += 2)
                  ans[P[p][i]] = 1;
            }
      }
      for (auto [op, p] : tp)
         now -= P[p].size() + (op == 2) >> 1;
   }
}
inline void Main() {
   int m;
   scanf("%d%d%d", &n, &m, &ed);
   for (int i = 1; i <= n; i++) to[i].clear();
   std::unordered_map<int, int> s;
   for (int x, y; m--; ) {
      scanf("%d%d", &x, &y);
      if (x > y) std::swap(x, y);
      if (s[x * n + y]++) continue;
      to[x].push_back(y), to[y].push_back(x);
   }
   for (int i = 1; i <= n; i++) deg[i] = to[i].size();
   mn = ed + 1, dfs();
   if (mn > ed) return puts("-1"), void();
   std::vector<int> U;
   for (int i = 1; i <= n; i++)
      if (ans[i]) U.push_back(i);
   printf("%d %zu\n", mn, U.size());
   for (int x : U) printf("%d ", x);
   puts("");
}
int main() {
   int T;
   scanf("%d", &T);
   while (T--) Main();
   return 0;
}