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;
}