NoRootTree 类

无根树生成器，用于生成无根树。

公开的枚举类型

NRT_GEN_CONF 枚举

名称	注释
METHOD_CHAIN	描述生成方案为生成链
METHOD_DAISY	描述生成方案为生成菊花图
METHOD_CHAIN_WITH_CHAIN	描述生成方案为生成链套链
METHOD_DAISY_WITH_DAISY	描述生成方案为生成菊花图套菊花图
METHOD_CHAIN_WITH_DAISY	描述生成方案为生成链套菊花图
METHOD_COMP_KB_TREE	描述生成方案为生成完全 \(K\) 叉树
METHOD_RND_TREE	描述生成方案为生成随机树
METHOD_TREE_OVER_TREE	描述生成方案为生成随机树套随机树

公开的成员

返回类型	函数定义
	NoRootTree(int verCount, int vmin, int vmax)
	NoRootTree(int verCount)
void	Generate(void)
void	SpecificGenerate(NRT_GEN_CONF method)
void	Output(bool shuffleOutput = true)

详细注解

NoRootTree 构造

描述：

无根树的构造函数。

语法：

带边权重载：

NoRootTree::NoRootTree(
    [in]    int verCount,
    [in]    int vmin,
    [in]    int vmax
);

无边权重载：

NoRootTree::NoRootTree(
    [in]    int verCount
);

参数：

• verCount：无根树的点数。
• vmin：无根树边权最小值（Override!!）
• vmax：无根树边权最大值（Override!!）

警告：

注意，两个重载之间本质不同！！请注意不要混用。

---

Generate 方法

描述：

启用无根树生成。

语法：

void NoRootTree::Generate(void);

注释：

使用这个函数，您将会有如下概率生成如下结构：

结构	概率
菊花图	\(5\%\)
链	\(5\%\)
链套链	\(15\%\)
菊花图套菊花图	\(15\%\)
链套菊花图	\(20\%\)
完全 \(K\) 叉树	\(15\%\)
随机树	\(15\%\)
随机树套随机树	\(10\%\)

---

SpecificGenerate 方法

描述：

生成特定树结构。

语法：

void NoRootTree::SpecificGenerate(
    [in]    NRT_GEN_CONF method
);

参数：

• method：生成方式，具体见枚举 NRT_GEN_CONF。

---

Output 方法

描述：

输出生成器的生成结果。

语法：

void NoRootTree::Output(
    [in, optional]  bool shuffleOutput
);

参数：

• shuffleOutput：打乱输出开关，默认为开启（true）

使用示例

洛谷 P3806 【模板】点分治1 的测试数据生成：

#include "genlib.h"
using namespace Generator;
void f(int label)
{
    FlushIOStream();
    int n, m;
    int minN = 1,maxN = 1e4;
    int minM = 1,maxM = 100;
    if(label <= 3)
        maxN = 100;
    else if(label <= 6)
        maxM = 50, maxN = 1e3;
    else
        minN = 2e3, minM = 50;
    n = irand(minN, maxN);
    m = irand(minM, maxM);
    cout << n << ' ' << m << endl;
    NoRootTree nrt(n, 1, 1e4);
    if(label == 8)
        nrt.SpecificGenerate(METHOD_CHAIN);
    else
        nrt.Generate();
    nrt.Output();
    while(m--)
        cout << irand(1, 1e7) << endl;
}
int main()
{
    AutoGenerate("dfz%d.in", 1, 9, f);
    return 0;
}

生成一张有 \(30\) 个点的菊花图：

#include "genlib.h"
using namespace Generator;
int main()
{
    RedirectToFile("in.in");
    NoRootTree nrt(30);
    nrt.SpecificGenerate(METHOD_DAISY);
    nrt.Output();
    return 0;
}