UOJ#460. 新年的拯救计划 构造

时间:2021-07-03 11:46:55

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ460.html

题解

  本题的构造方法很多。这里只介绍一种。

  首先,总边数为 $\frac{n(n-1)}2$,每一棵树需要 $n-1$ 条边,所以答案最多是 $\lfloor \frac n 2 \rfloor$ 。

  然后我们来找到构造出 $\lfloor \frac n 2 \rfloor$ 。

  这里我们只考虑 n 为偶数,因为如果 n 为奇数的话就只要在 n-1 的基础上随便连就好了。

  考虑增量法。

  假设当前加入的点为 n-1 和 n ,那么,首先我们在原来的 $\frac {n-2} 2 $ 个树中连上点 n-1 和 n,方法是对于第 $i$ 棵树,$2i-1$ 连 $n-1$, $2i$ 连 $n$;

  接下来我们考虑搞一个新树。首先 $n-1$ 连 $n$ ,然后对于 $1$~$n-2$,偶数连 $n-1$,奇数连 $n$ 。

  构造完毕。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read(){
LL x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
const int N=2005;
int n;
vector <pair <int,int> > e[N];
int main(){
n=read();
for (int i=2;i<=n;i+=2){
int j=i-1;
e[i/2].push_back(make_pair(i,j));
for (int a=2;a<i;a+=2){
int b=a-1;
e[a/2].push_back(make_pair(a,i));
e[a/2].push_back(make_pair(b,j));
e[i/2].push_back(make_pair(a,j));
e[i/2].push_back(make_pair(b,i));
}
}
if (n&1)
for (int i=1;i<=n/2;i++)
e[i].push_back(make_pair(i*2,n));
printf("%d\n",n/2);
for (int i=1;i<=n/2;i++,puts(""))
for (auto p : e[i])
printf("%d %d ",p.first,p.second);
return 0;
}