清真的构造题
题意
求将$ n$个点的完全图划分成最多的生成树的数量，并输出一种构造方案
题解
首先一棵生成树有$ n-1$条边，而原完全图只有$\frac{n·(n-1)}{2}$条边
因而最多的生成树数量仅为$\frac{n}{2}$
只考虑$ n$为偶数的情况(n为奇数时所有生成树中随便挑一个点往新点连边即可)
当$n=2$时生成树为(1,2)
当$ n >2$时先将$ n$和$ n-1$连边
然后将对于$ 1 \leq i <n-1$,如果$ i$是奇数就将$ (i,n)$加入$ n$所在的生成树，将$ (i,n-1)$加入$ i$所属的生成树
否则将$ (i,n)$加入$ i$所属的生成树，将$ (i,n-1)$加入$ n$所属的生成树
这样就构造完毕了
代码
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans;
void print(int x,int y){
write(x);putchar(' ');write(y);putchar(' ');
}
int main(){
n=read();
writeln(n/);
for(rt i=;i+<=n;i+=){
print(i,i+);
for(rt j=;j<i;j++)if(j&)print(i,j);else print(i+,j);
for(rt j=i+;j<=n;j++)if(j&)print(i+,j);else print(i,j);
putchar('\n');
}
return ;
}