题解：P15653 [省选联考 2026] 星图 / starmap

tiger2005 · 2026-03-08 23:28:34 · 题解

这里介绍一个可能比较好写的做法，借鉴了很多前辈的智慧。

首先，将整个图的边取反，也就是读入的边反而不被存储。此时问题的目标就从最大化边数变成了最小化边数。

在开始接下来的讨论之前，不妨观察一个通过完全图边集的异或和可以构造的结构：

::::success[四元环]{open} 对于任意的四个点 a, b, c, d，可以任意选择这四个点之外的 k-2 个点 x_1, x_2, \dots, x_{k-2}，并通过如下四步得到一个四元环 a - b - c - d - a：

(x_1, x_2, \dots, x_{k-2}, a, b),\\ (x_1, x_2, \dots, x_{k-2}, b, c),\\ (x_1, x_2, \dots, x_{k-2}, c, d),\\ (x_1, x_2, \dots, x_{k-2}, d, a).

::::

在四元环可构造的前提下，可以得到如下定理：

::::info[定理]{open} 如果一个图满足：

所有点度数均为偶数；
边数也为偶数，

那么存在一种方案，仅通过异或四元环消除图中所有的边。 ::::

::::success[方案构造]{open} 首先，由于 1 号点的度数为偶数，不妨考虑 1 的两条邻边 1 - u 和 1 - v。任选一个点 w 后，异或上四元环 1 - u - w - v - 1，即可将这两条边消除。重复此过程直到 1 号点的度数变为 0。

随后，对剩下的每个连通块，总能找到一个欧拉回路（因为所有点的度数均为偶数）。利用异或的性质，可以通过相同的边将两个回路相连，最终将所有欧拉回路合并为一个整体。记该欧拉回路如下：

a_1 \to b_1 \to a_2 \to b_2 \to \dots \to a_q \to b_q \to a_1

则可用如下四边形消除整个欧拉回路：

1 - a_1 - b_1 - a_2 - 1,\\ 1 - a_2 - b_2 - a_3 - 1,\\ \dots \\ 1 - a_q - b_q - a_1 - 1.

::::

基于上述性质，第一个询问的本质可转化为：在原图中至少需要修改几条边的状态，才能使修改后的图在若干次操作之后满足“所有点度数均为偶数且边数为偶数”？这里需要注意到，每次操作会使得 k 个点周围 k-1 条边的状态发生变化，总共会影响 \frac {k(k-1)} 2 条边的状态。此时：

若 k-1 为奇数，则总可通过如下两次操作将两个奇度点 u, v 变为偶度，而不影响其他点度数的奇偶性： (u, x_1, x_2, \dots, x_{k-1}),\\ (v, x_1, x_2, \dots, x_{k-1}).
因此点度数的奇偶性不重要。反之，若 k-1 为偶数，则修改后所有点的度数必须为偶数。
若 \frac {k(k-1)} 2 为奇数，则总可通过一次操作将奇边数的图变为偶边数，因此边数的奇偶性不重要。反之，若 \frac {k(k-1)} 2 为偶数，则修改后的边数必须为偶数。

为讨论 k-1 和 \frac {k(k-1)} 2 的奇偶性，根据 k \bmod 4 分类如下：

:::align{center}

k \bmod 4	点度数要求	边数要求	修改方案
0	无要求	必须为偶数	若边数为奇数，则随意修改一条边的状态
1	必须为偶数	必须为偶数	先将奇度点两两配对，若边数为奇数，则再修改一个三角形（可抵消之前的配对边）
2	无要求	无要求	无需操作
3	必须为偶数	无要求	将奇度点两两配对

:::

根据上表即可确定需要修改的边数，将其从 \frac {n(n-1)} 2 中减去即得第一个问题的答案。

接下来是构造部分。构造主要分为两个步骤：

当 n > k + 2 时，将图的规模从 n 缩小至 n-1，即消除 n 号点的所有邻边。为保证剩余图结构形成子问题，还需确保操作次数不超过 n-1。

对于 n 号点的两条邻边 n - u 和 n - v，可通过如下两次操作消除，且不影响其他邻边：
(n, u, x_1, x_2, \dots, x_{k-2}),\\ (n, v, x_1, x_2, \dots, x_{k-2}),
这样即可处理 n 号点度数为偶数的情况。若 n 号点度数为奇数，则可通过一次操作调整其奇偶性（若 k-1 为偶数，则 n 号点度数不可能为奇数）。为防止该额外操作导致总次数超过 n-1，选点时必须包含至少一条已有的邻边。
当 n = k + 2 时，进行如下处理：
- 若边数为奇数，则通过一次操作将其调整为偶数；
- 将所有奇度点两两配对，通过两次操作处理每个配对；
- 此时图已满足偶度数、偶边数，利用前述四边形策略消除所有边。

至此完成构造，时间复杂度可以做到 \mathcal{O} (\sum {n^2 k})，是理论上的最低复杂度。

::::info[代码]

// https://qoj.ac/submission/2111420

#include "starmap.h"
#include <cassert>
#include <bitset>
#include <algorithm>
using namespace std;

void init(int c, int t) { }

bitset<510> w[510];

bitset<510> emit_bs[510];

int mex(int a, int b) {
  int r = 1;
  while (r == a || r == b) ++ r;
  return r;
}

int mex(int a, int b, int c) {
  int r = 1;
  while (r == a || r == b || r == c) ++ r;
  return r;
}

void starmap(int n, int m, int k, int p, std::vector<int> _u, std::vector<int> _v) {
  for (int i = 1; i <= n; i ++) {
    w[i].reset();
    emit_bs[i].reset();
    for (int j = 1; j <= n; j ++)
      w[i][j] = (i != j);
  }

  for (int i = 0; i < m; ++i)
    w[_u[i]][_v[i]] = w[_v[i]][_u[i]] = false;

  auto flip = [&] (int u, int v) {
    w[u][v] = w[v][u] = !w[u][v];
  };

  if (k % 4 == 2) {
    report(n * (n - 1) / 2);
  } else if (k % 4 == 0) {
    int r = n * (n - 1) / 2;
    if ((r + m) % 2)
      flip(1, 2), -- r;
    report(r);
  } else if (k % 4 == 3) {
    vector<int> odd, even;
    for (int i = 1; i <= n; i ++)
      (w[i].count() & 1 ? odd : even).push_back(i);
    int r = n * (n - 1) / 2;
    for (int i = 0; i < (int)odd.size(); i += 2)
      flip(odd[i], odd[i + 1]), -- r;
    report(r);
  } else {
    vector<int> odd, even;
    for (int i = 1; i <= n; i ++)
      (w[i].count() & 1 ? odd : even).push_back(i);
    int r = n * (n - 1) / 2;
    for (int i = 0; i < (int)odd.size(); i += 2)
      flip(odd[i], odd[i + 1]), -- r;
    if ((r + m) & 1) {
      if (odd.empty()) {
        flip(1, 2); flip(2, 3); flip(3, 1);
        r -= 3;
      } else {
        int u = odd[0], v = odd[1];
        int w = 1;
        while (w == u || w == v) ++ w;
        flip(u, v); flip(v, w); flip(w, u);
        -- r;
      }
    }
    report(r);
  }

  // 将 n 缩减至 k+2
  {
    auto outer_invert = [&] (vector<int> v) {
      bitset<510> temp;
      temp.reset();
      for (auto e : v) temp[e] = 1;
      for (auto e : v) w[e] ^= temp, w[e][e] = false;
      invert(v);
    };

    for (int cur = n; cur > k + 2; cur --) {
      vector<int> targ;
      if (w[cur].count() & 1) {
        assert(k % 2 == 0);
        int base = -1;
        for (int j = 1; j < cur; j ++) if (w[cur][j]) {
          base = j; break;
        }
        vector<int> vec;
        for (int j = 1; vec.size() != k - 2; j ++)
          if (j != base) vec.push_back(j);
        vec.push_back(base);
        vec.push_back(cur);
        outer_invert(vec);
      }

      vector<int> nums;
      for (int j = 1; j < cur; j ++) if (w[cur][j])
        nums.push_back(j);
      for (int p = 0; p < (int)nums.size(); p += 2) {
        int u = nums[p], v = nums[p + 1];
        vector<int> vec;
        for (int j = 1; vec.size() != k - 2; j ++)
          if (j != u && j != v) vec.push_back(j);
        vec.push_back(cur);
        vec.push_back(u); outer_invert(vec);
        vec.back() = v; outer_invert(vec);
      }

      assert(w[cur].count() == 0);
    }

    n = k + 2;
  }

  // 剩余的部分
  {
    // 只传入没有出现的两个值
    auto inner_emit = [&] (int u, int v) {
      assert(u != v);
      if (u > v) swap(u, v);
      emit_bs[u][v] = !emit_bs[u][v];
    };

    // 通用，反转一个四元环
    auto C4 = [&] (int a, int b, int c, int d) {
      inner_emit(a, b);
      inner_emit(b, c);
      inner_emit(c, d);
      inner_emit(d, a);
      flip(a, b); flip(b, c); flip(c, d); flip(d, a);
    };

    // 调整边数
    int edges = 0;
    for (int i = 1; i <= n; i ++) edges += w[i].count();
    if (edges % 4 == 2) {
      assert(k % 4 >= 2);
      inner_emit(1, 2);
      for (int u = 3; u <= n; u ++)
        for (int v = u + 1; v <= n; v ++)
          flip(u, v);
    }

    // 调整度数
    if (k % 2 == 0) {
      vector<int> odd;
      for (int i = 1; i <= n; i ++) if (w[i].count() & 1)
        odd.push_back(i);
      for (int i = 0; i < (int)odd.size(); i += 2) {
        int u = odd[i], v = odd[i + 1];
        int base = mex(u, v);
        inner_emit(u, base);
        inner_emit(v, base);
        for (int p = 1; p <= n; p ++)
          if (p != u && p != v && p != base)
            flip(u, p), flip(v, p);
      }
    }

    // 孤立出 1 号点
    int base = -1;
    for (int i = 2; i <= n; i ++) if (w[1][i]) {
      if (base == -1) base = i;
      else {
        int u = mex(1, base, i);
        C4(1, base, u, i);
        base = -1;
      }
    }
    assert(base == -1);

    vector<int> paths;
    // 对剩余点跑欧拉回路，用四元环消除
    auto dfs = [&] (auto self, int x) -> void {
      for (int i = 1; i <= n; i ++) if (w[x][i])
        flip(x, i), self(self, i);
      paths.push_back(x);
    };

    for (int i = 2; i <= n; i ++) if (w[i].count()) {
      dfs(dfs, i);
      if (base == -1) base = i;
      else paths.push_back(base);
    }

    for (int i = 0; i < (int)paths.size() - 2; i += 2) {
      int a = paths[i], b = paths[i + 1], c = paths[i + 2];
      if (a != c) C4(1, a, b, c);
    }

    for (int u = 1; u <= n; u ++)
      for (int v = u + 1; v <= n; v ++) if (emit_bs[u][v]) {
        vector<int> vec;
        for (int j = 1; j <= n; j ++) if (j != u && j != v)
          vec.push_back(j);
        invert(vec);
      }
  }
}

::::