清真的构造题
求将$ 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=0;char zf=1;char ch=getchar(); while(ch!=‘-‘&&!isdigit(ch))ch=getchar(); if(ch==‘-‘)zf=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();return x*zf; } void write(ll y){if(y<0)putchar(‘-‘),y=-y;if(y>9)write(y/10);putchar(y%10+48);} 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/2); for(rt i=1;i+1<=n;i+=2){ print(i,i+1); for(rt j=1;j<i;j++)if(j&1)print(i,j);else print(i+1,j); for(rt j=i+2;j<=n;j++)if(j&1)print(i+1,j);else print(i,j); putchar(‘\n‘); } return 0; }
原文：https://www.cnblogs.com/DreamlessDreams/p/10409139.html