题解 P6575 【[BOI 2017] Friends】

· · 题解

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

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

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

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

这是一道有趣的暴力题。

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

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

对于第一个步骤，用暴力去枚举所有过 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;
}

参考资料