problem

一张 n 个点的完全图, 问是否能给出若干个三元环或是四元环, 覆盖每条边恰好 2

  • n\leq 300

sol

又不是很会啊, 学到了学到了.

分奇偶讨论, 先研究n\bmod 2 \equiv 0的情况.

  • 考虑数学归纳法

我们已经求好了n规模的问题 (n=4显然可以手玩)

且答案中存在这样的三元环(1,2,x)\ (3, 4, y) \dots (n-1, n, z)

x,y,z并不关键, 只是一个数而已.

a=n+1, b=n+2.

那么我们就要在原图上加上(a,1), (a,2)等等的边.

考虑三元环(1, 2, x), 将其替换为 (1, a, 2, x),(1, a, 2, b),(1, 2, b)就满足条件了

对于 (3, 4, y),(5, 6, z) 同理.

最后, 由于要覆盖两次 (a, b), 还需将最开始的(1, a, 2, b) 替换为 (a, b, 1)(a, b, 2).

n 为奇数时,从 n = 3 开始添加 a, b.

(2, 3, x),(4, 5, y) 同上替换为两个四元环和一个三元环

最后剩下(a,1)(b,1)的边未覆盖

再加入两个 (1, a, b)即可.

Code

#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> Vec;

int n, a, b, one, two, x;
Vec ans, last;

inline void add3(int a, int b, int c) {
  ans.push_back({a, b, c});
}
inline void add4(int a, int b, int c, int d) {
  ans.push_back({a, b, c, d});
}

int main() {
  scanf("%d", &n);
  if(n % 2 == 0) {
    add3(1, 2, 3);
    add3(3, 4, 2);
    for(int step = 4; step < n; step += 2) {
      a = step + 1;
      b = step + 2;
      for(int j = 0; j < (int) ans.size(); ++j)
        if((int) ans[j].size() == 3) {
          one = ans[j][0];
          two = ans[j][1];
          x = ans[j][2];
          add4(one, a, two, x);
          add4(one, a, two, b);
          ans[j] = {one, two, b};
        }
      one = ans[ans.size() - 1][0];
      two = ans[ans.size() - 1][2];
      ans.pop_back();
      add3(a, b, one);
      last.push_back({a, b, two});
    }
    add3(1, 2, 4);
    add3(1, 3, 4);
    printf("%d\n", ans.size() + last.size());
    for(int i = 0; i < (int) ans.size(); ++i) {
      printf("%d ", ans[i].size());
      for(int j = 0; j < (int) ans[i].size(); ++j)
        printf("%d ", ans[i][j]);
      puts("");
    }
    for(int i = 0; i < (int) last.size(); ++i) {
      printf("%d ", last[i].size());
      for(int j = 0; j < (int) last[i].size(); ++j)
        printf("%d ", last[i][j]);
      puts("");
    }
  } else {
    add3(2, 3, 1);
    last.push_back({2, 3, 1});
    for(int step = 3; step < n; step += 2) {
      a = step + 1;
      b = step + 2;
      for(int j = 0; j < (int) ans.size(); ++j)
        if((int) ans[j].size() == 3) {
          one = ans[j][0];
          two = ans[j][1];
          x = ans[j][2];
          add4(one, a, two, x);
          add4(one, a, two, b);
          ans[j] = {one, two, b};
        }
      last.push_back({a, b, 1});
      add3(a, b, 1);
    }
    printf("%d\n", ans.size() + last.size());
    for(int i = 0; i < (int) ans.size(); ++i) {
      printf("%d ", ans[i].size());
      for(int j = 0; j < (int) ans[i].size(); ++j)
        printf("%d ", ans[i][j]);
      puts("");
    }
    for(int i = 0; i < (int) last.size(); ++i) {
      printf("%d ", last[i].size());
      for(int j = 0; j < (int) last[i].size(); ++j)
        printf("%d ", last[i][j]);
      puts("");
    }
  }
  return 0;
}