UOJ460 新年的拯救计划

神仙构造题…没智商..

考虑构造出一棵树$T_0$，对于$T_0$中的任意一条边$(u,v)$，我们在第k$(0<k\leq \lfloor\frac n 2\rfloor)$棵树中添加边$((u+k)~mod~n,(v+k)~mod~n)$。

现在考虑什么样子的$T_0$能保证对于任意$k_1\neq k_2$，均满足$((u+k_1)~mod~n,(v+k_1)~mod~n)\neq ((u+k_2)~mod~n,(v+k_2)~mod~n)$。

首先答案一定有$\lfloor \frac n 2 \rfloor$棵生成树，那么我们可以考虑把点集分成两半，每个点集里面的边全都从某个点出发，这样我们只需要变化这个出发点，其他所有边也会跟着平移，就可以保证所有边不重复。

设$m=\lfloor \frac n 2\rfloor$，首先令点编号从0开始。

首先连边$(0,m)$，这条边显然在任何一棵树中都不会重复。

对于$1\leq i\leq m-1$,连边$(0,i)$.

对于$ m<i<n$,连边$(m,i)$。

这样在$0+k和m+k$不重复的情况下，任何生成树内一定不会出现重复边了。

#include <algorithm>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using int_t = long long int;
using pair_t = std::pair<int_t, int_t>;
using std::cin;
using std::cout;
using std::endl;
std::vector<pair_t> edges;
int main() {
    int_t n;
    cin >> n;
    int_t mid = n / 2;
    edges.push_back(pair_t(0, mid));
    for (int_t i = 1; i < mid; i++) {
        edges.push_back(pair_t(0, i));
    }
    for (int_t i = mid + 1; i < n; i++) {
        edges.push_back(pair_t(mid, i));
    }
    cout << n / 2 << endl;
    for (int_t i = 0; i < n / 2; i++) {
        for (const auto& edge : edges) {
            int_t a, b;
            std::tie(a, b) = edge;
            cout << (a + i) % n + 1 << " " << (b + i) % n + 1 << " ";
        }
        cout << endl;
    }
    return 0;
}