自动搬运

查看原文

来自洛谷，原作者为

	Tweetuzki AFO

搬运于2025-08-24 22:22:04，当前版本为作者最后更新于2020-05-27 17:49:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

给出一张 $n$ 个点，$m$ 条边的无向图。

需要将这些点划分为若干互不相交的点集，满足：

• 集合大小不超过 $p$。
• 这个集合内的点连出集合的边不超过 $q$ 条。

判断是否有解并给出合法方案。

$n \le 2500$，$p + q \le 15$，$m \le 15\ 000$。

这是一道有趣的暴力题。

首先有个小细节，要先检查一遍原图是否是一张无向图（即 $u \to v$ 有边是否同时会保证 $v \to u$ 有边），如果不是需要直接输出 detention，详见样例 3，因为这被当做是同学撒谎（（（。

我们将算法分为两个步骤：

• 对 $1 \sim n$ 中的每个点 $i$，找出一个包含 $i$ 的合法的集合。如果找不到，说明无解，输出 detention。
• 对求出的所有点集，调整方案，使得原本的任意两个点集 $S, T$ 变成 $S', T'$，使得 $S' \cap T' = \emptyset$ 且 $S' \cup T' = S \cup T$。这样处理后最后每个点就仅属于一个点集。

对于第一个步骤，用暴力去枚举所有过 $i$ 的联通块，当连通块大小超过 $p$ 或连通块大小加上相邻点集大小超过 $p + q$ 时就退出递归。这样暴力复杂度可以证明是 $\mathcal{O}(2 ^ {p + q})$，做 $n$ 次就是 $\mathcal{O}(n \cdot 2 ^ {p + q})$。

一种理解是，我们首先将问题进行缩放，定义 $q'$ 为集合外的与集合内的点有连边的点数，显然 $q' \le q$。

我们给每个点四种状态：在集合内、与集合内的点相邻但还未确定是否要加入集合、与集合内的点相邻且确定不加入集合、不与集合相邻的点（前三者在我的代码中分别体现为 $\texttt{std::set<int> in, neighbor, out}$）。

当我们递归到连通块 $s$ 时，我们只枚举那些与集合内的点相邻但还未确定是否要加入集合的点（即 $\texttt{neighbor}$）。这样，若加入该点到集合内，则 $p$ 增加 $1$；如果不加入该点到集合内，则 $q'$ 增加 $1$。也就是说，在每步递归的过程中，共有两种选择，而每做一层 $p + q'$ 的值都会增加，故而最多做 $p + q'$ 层。又由于 $q' \le q$，因此递归次数上界为 $2 ^ {p + q}$。

对于第二个步骤，有一个结论：对于两个合法的点集 $A, B$，则 $A \setminus B$ 和 $B \setminus A$ 中必然至少有一个是合法点集。

证明为，设 $C = A \cap B$，$A, C$ 之间边数为 $a$，$B, C$ 之间边数为 $b$，$C$ 向外且不连向 $A, B$ 的边数为 $c$。则当 $A$ 变成 $A \setminus B$ 后，边数加上了 $a - b - c$，$B$ 变成 $B \setminus A$ 后，边数加上了 $b - a - c$。由于 $a - b$ 和 $b - a$ 互为相反数，则其中至少一个 $\le 0$，则 $p + q$ 的值不会变大，一定还是合法的点集。

知道了这个结论后，我们可以枚举 $n \choose 2$ 个点对，调整他们的点集 $(S, T)$ 变成 $(S \setminus T, T)$ 或 $(S, T \setminus S)$，就可以使得所有集合无交了。这里复杂度 $\mathcal{O}(n ^ 2 p)$。

总时间复杂度 $\mathcal{O}(n \cdot 2 ^ {p + q} + n ^ 2 p)$，实际很难卡满，常数不大，可以通过本题。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <vector>

const int MaxN = 2500, MaxM = 30000;
const int MaxP = 15;

struct graph_t {
  int cnte;
  int head[MaxN + 5], to[MaxM * 2 + 5], next[MaxM * 2 + 5];

  inline void addEdge(int u, int v) {
    cnte++; to[cnte] = v;
    next[cnte] = head[u]; head[u] = cnte;
  }
};

int N, P, Q;
graph_t Gr;
std::set<int> Group[MaxN + 5];
bool InGroup[MaxN + 5];

void NO() { puts("detention"); exit(0); }

void init() {
  std::set< std::pair<int, int> > edge;
  edge.clear();
  scanf("%d %d %d", &N, &P, &Q);
  for (int i = 0; i < N; ++i) {
    int m;
    scanf("%d", &m);
    if (m >= P + Q) NO();
    for (int j = 1; j <= m; ++j) {
      int x;
      scanf("%d", &x);
      Gr.addEdge(i + 1, x + 1);
      if (i < x) edge.insert(std::make_pair(i, x));
      else {
        if (edge.count(std::make_pair(x, i)) == 0) NO();
        else edge.erase(std::make_pair(x, i));
      }
    }
  }
  if (edge.empty() == false) NO();
}

inline bool validGroup(const std::set<int> &s) {
  if ((int) s.size() > P) return false;
  int cnt = 0;
  for (int u : s) {
    for (int i = Gr.head[u]; i; i = Gr.next[i]) {
      int v = Gr.to[i];
      if (s.count(v) == 0) cnt++;
    }
  }
  return cnt <= Q;
}

std::set<int> in, neighbor, out;

bool dfs(int u, int bel, std::set<int> in, std::set<int> neighbor, std::set<int> out) {
  in.insert(u);
  if (u != bel) neighbor.erase(u);
  if ((int) in.size() > P || (int) out.size() > Q || (int) in.size() + (int) neighbor.size() + (int) out.size() > P + Q) return false;
  if (validGroup(in) == true) {
    Group[bel] = in;
    for (int v : in) InGroup[v] = true;
    return true;
  }
  for (int i = Gr.head[u]; i; i = Gr.next[i]) {
    int v = Gr.to[i];
    if (in.count(v) == 0 && neighbor.count(v) == 0 && out.count(v) == 0)
      neighbor.insert(v);
  }
  while (!neighbor.empty()) {
    int v = *(neighbor.begin());
    if (dfs(v, bel, in, neighbor, out) == true) return true;
    neighbor.erase(neighbor.begin());
    out.insert(v);
  }
  return false;
}

void solve() {
  for (int i = 1; i <= N; ++i) {
    if (InGroup[i] == true) continue;
    in.clear();
    neighbor.clear();
    out.clear();
    if (dfs(i, i, std::set<int>(), std::set<int>(), std::set<int>()) == false) NO();
  }
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j < i; ++j) {
      std::set<int> s1 = Group[i], s2 = Group[j];
      for (int v : Group[i])
        if (s2.count(v) > 0) s2.erase(v);
      for (int v : Group[j])
        if (s1.count(v) > 0) s1.erase(v);
      if (validGroup(s1) == true) Group[i] = s1;
      else Group[j] = s2;
    }
  int cntGroup = 0;
  for (int i = 1; i <= N; ++i)
    if (Group[i].empty() == false) cntGroup++;
  puts("home");
  printf("%d\n", cntGroup);
  for (int i = 1; i <= N; ++i) {
    if (Group[i].empty()) continue;
    printf("%d", (int) Group[i].size());
    for (int v : Group[i]) printf(" %d", v - 1);
    putchar('\n');
  }
}

int main() {
  init();
  solve();
  return 0;
}

参考资料