自动搬运

查看原文

来自洛谷，原作者为

	rizynvu w

搬运于2025-08-24 22:46:50，当前版本为作者最后更新于2024-07-01 21:14:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的博客。

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$。

• 若最大度数 $\le 2$，那么只有环和链，可以直接处理。
  对于环，最小覆盖即为 $\lceil\frac{len}{2}\rceil$，每个点都有可能被选入。
  对于链，分讨一下长度 $len$ 的奇偶：
  1. 为偶，则最小覆盖为 $\frac{len}{2}$，每个点都有可能。
  2. 为奇，则最小覆盖为 $\lfloor\frac{len}{2}\rfloor$，只有选择按顺序的第 $2, 4, \cdots$ 的点是最优的。
• 若最大度数 $> 3$，那么就用上文提到的朴素递归。

考虑复杂度，令 $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;
}