Tree Constructing
Tree Constructing
CF 494 E
这次是div3的题目，本身没有涉及到什么复杂的算法，可以说就是一道模拟题。不过细节还是很多的，需要注意。比赛时因为漏掉了一个细节结果比赛后被hack了，否则这次div3能排到一百多名(〒▽〒)。。。。
题解
题目要求给定顶点数n,直径d,和最大度数k，是否有这样的数存在。存在的话输出这棵树的所有边。
首先，这里的n和d都是必须正好满足的，而k则是要求树最大度数小于等于k即可。所以，在这里，我们应该先从d入手。
很明显，我们可以首先尝试构建一个最长边，它总共包含d+1个点。所以，若$ n d $，就可以直接输出"NO"。
而当我们构建最长边时，若\(d+1==1\)，则必须满足\(k\ge0\)；若$ d+1==2\(，则必须满足\)k\(;若\)d+1\(,则必须满足\) k $。所以若以上条件不满，我们也可以输出"NO"。
在最长边构建完成之后，我们便可以开始构建其他的边了。很明显，其他的边都是由最长边上的点为根节点延伸出来的，也就是说，其他的边集构成了一个根节点为最长边上的点的若干个子树。所以说，我们在最长边上一直生成子树，就能够形成一个满足最终条件的树。
当然，也存在不满足条件的情况。若我们已经构建了所有满足情况的子树之后，结点数还是小于n的话，说明无法构建，此时应该输出"NO"。
还有，我们该如何生成一个符合条件的子树呢？我们可以使用一个递归的建树函数，分别传入该点的序号，该点剩余的度数和该点向下还能够建树的深度。这样的话当深度为0是直接返回，从而使我们生成的子树不会令最长边变长。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <iostream>
using namespace std;
int n,d,k;
int cur;
int ans[400100][2];
int num = 0;
void build(int x,int t,int kk)
{
trueif (t==0)
truetruereturn;
trueif (cur>n)
truetruereturn;
truefor (int i = 0; i<kk; i++)
true{
truetrueans[num][0] = x;
truetrueans[num][1] = cur;
truetruecur ++;
truetruenum ++;
truetrueif (cur > n)
truetruetruereturn;
truetruebuild(cur-1,t-1,k-1);
truetrueif (cur > n)
truetruetruereturn;
true}
}
int main()
{
truecin >> n >> d >> k;
trued++;
trueif (n < d || (d>2 && k==1) )
true{
truetruecout << "NO";
truetruereturn 0;
true}
truefor (int i = 1; i<d; i++)
true{
truetrueans[num][0] = i;
truetrueans[num][1] = i+1;
truetruenum++;
true}
truecur = d+1;
truefor (int i = 1; i<=d; i++)
truetruebuild(i,min(i-1,d-i),k-2);
true
trueif (num!=n-1)
truetruecout << "NO" << endl;
trueelse{
truetruecout << "YES" << endl;
truetruefor (int i = 0; i<num; i++)
truetruetruecout << ans[i][0] << " " << ans[i][1] << endl;
true}
}
|