UOJ460 新年的拯救计划题解

题意：

给定一个 \(n\) 阶完全图 \(K_n\) ，你需要构造 \(K_n\) 的 \(m\) 棵不相交的生成树，求 \(m\) 的最大值并给出方案。

输入格式：

共一行，包含一个正整数 \(n (3\le n\le 2000)\)，表示图的阶数。

输出格式：

输出的第一行是一个正整数 \(m\)，表示生成树的个数。

接下来 \(m\) 行，每行 \(2(n−1)\) 个数，描述一棵生成树，其中第 \(2i−1\) 和第 \(2i\) 个数表示树中的一条边。

你需要保证你输出的 \(m\) 个子图为 \(K_n\) 的 \(m\) 棵不相交生成树。

如果有多组解，输出任意一组均可。

还在咕咕咕，因为不是很懂。。

口糊了一下dp然后发现方案数是可以 \(\mathcal{O}(1)\) 的，结果不会构造（悲。然后瞄了眼题解发现dp是错的（悲*2

直接说正解吧，方案数为 \(\left\lfloor\frac{n}{2}\right\rfloor\) 。

证明：首先 \(n\) 阶完全图有 \(\frac{n(n-1)}{2}\) 条边，很显然

而生成树有 \(n-1\) 条边，所以至多有 \(\left\lfloor\frac{n}{2}\right\rfloor\) 棵不相交的生成树。\(\square\)

考虑构造。这里先给出官方题解的构造（其实我也不是很懂

因为要恰好 \(\left\lfloor\frac{n}{2}\right\rfloor\) 棵生成树，所以当 \(n\) 为偶数时，每一条边都要用上。

我们先构造一棵树 \(T_0\) ，然后对于 \(T_0\) 中的每条边 \((u,v)\) ，向 \(T_i\) 中添加边 \(\left((u+i) \bmod n,(v+i) \bmod n\right)\) 。

那么怎么构造这个 \(T_0\) 呢？

定义一条边 \((u,v)~(u < v)\) 的长度为 \(\min\{v-u,u-v+n\}\) ，

则在 \(T_0\) 中一定恰好包含了长为 \(1\) 到 \(\frac{n}{2} - 1\) 的边各两条，和一条长为 \(\frac{n}{2}\) 的边。

考虑提出那条长为 \(\frac{n}{2}\) 的边，不妨假设其端点为 \(1\) 和 \(\frac{n}{2} + 1\) ，

我们只要让 \(1\) 和 \(2\) 到 \(\frac{n}{2}\) 之间的点连边，\(\frac{n}{2} + 1\) 和 \(\frac{n}{2} + 2\) 到 \(n\) 之间的点连边即可。

上面是 \(n\) 为偶数的情况，当 \(n\) 为奇数时也是合法的。

yhx 巨佬的构造就是下图中的“之字形”构造，还是比较好懂的。

但是原理我也没懂，貌似和std是同一种？有待研究。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define p(x) ((x + o) % n + 1)
#define N ((int)())

int n;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; cout << n/2 << '\n';
    for(int o=0; o<n/2; o++)
        for(int g = 1, i=n, j=n+1; g < n; ((++g) & 1) ? ++j : --i)
            cout << p(i) << ' ' << p(j) << " \n"[g == n-1];
    return 0;
}