随机树生成器
题目描述:
小Y最近有了一个随机数生成器(random number generator)。小Y想用这个随机数生成器生成 个节点的树。树为一种没有环的无向连通图。
经过小Y的研究，她发现了 种随机树生成方法。
第一种方法为首先生成一个 到 的全排列 。接着对于所有的节点 ，由 向 连一条边，其中 是 到 中的随机整数。
第二种方法为首先生成一个 到 的全排列 。接着对于所有的节点 ，由 向 连一条边，其中 是 到 中的随机整数。
第三种方法为首先有一个 个点的图，里面没有边。接着等概率地随机生成点对 ，如果当前图中 不连通，那么将边 加入到图中。重复这个过程，直到这个图连通为止。
第四种方法为在所有 个点的不同的有标号的树中，等概率地随机选取一棵树。两个树是不同的当且仅当存在一条边 只出现在其中一棵树中。比如 和 是两棵不同的树。
小Y用这四种方法生成了很多棵 个节点的树，但她忘记了这些树分别由哪种方法生成的。你能帮帮她辨认这些树由哪种随机方法生成吗？
在这个题目中令 ，也就是小Y生成的树的节点个数都为 。
输入格式:
第一行包含 个正整数 ，表示是第 组测试数据。
接下来一个正整数 ，表示有 棵树。
对于每棵树，共 行。每行包含 个正整数 ，表示这棵树中有一条节点 与节点 之间的边。
输出格式:
输出共 行，每行一个 到 之间的正整数，表示这棵树随机生成的方式。
样例输入:
见选手目录下的rng/rng.in与rng/rng.ans。
样例输出:
见选手目录下的rng/rng.in与rng/rng.ans。
提示:
【数据规模和约定】
对于所有的测试数据，保证输入的树是由上述四种方式随机生成。
各测试点满足以下约定：
|
测试点 |
m |
约定 |
|
1 |
=2000 |
只会出现第1，2种生成方式 |
|
2 |
=3000 |
只会出现第1，2，3种生成方式 |
|
3 |
=3000 |
只会出现第1，3，4种生成方式 |
|
4 |
=4000 |
无 |
|
5 |
=4000 |
无 |
对于每个测试点，保证每种可能出现的生成方式恰好出现 次。
【评分方法】
对于每个测试点，有 个评分参数 。
如果你的输出中错误的答案个数为 那么你将获得 的分数，其中 为满足 最大的整数。如果 ，那么你将获得 分。
如果输出格式有异常你将同样获得 分，请确保你的输出中共有 行，每行为一个 到 之间的正整数。
对于每个测试点的具体评分参数见选手目录下的rng/scores。
2016年全国青少年信息学奥林匹克浙江省队选拔赛第一试
竞赛时间：2016年3月24日 8:00-13:00
|
题目名称 |
随机树生成器 |
旅行者 |
小星星 |
|
目录 |
rng |
tourist |
star |
|
可执行文件名 |
rng |
tourist |
star |
|
输入文件名 |
rng.in |
tourist.in |
star.in |
|
输出文件名 |
rng.out |
tourist.out |
star.out |
|
每个测试点时限 |
3秒 |
2秒 |
1秒 |
|
内存限制 |
256MB |
512MB |
512MB |
|
测试点数目 |
5 |
10 |
10 |
|
每个测试点分值 |
20 |
10 |
10 |
|
是否有部分分 |
是 |
否 |
否 |
|
题目类型 |
传统型 |
传统型 |
传统型 |
|
是否有附加文件 |
是 |
是 |
是 |
提交源程序须加后缀
|
对于C++ 语言 |
rng.cpp |
tourist.cpp |
star.cpp |
|
对于C 语言 |
rng.c |
tourist.c |
star.c |
|
对于Pascal语言 |
rng.pas |
tourist.pas |
star.pas |
编译开关
|
对于C++ 语言 |
-O2 -lm |
-O2 -lm |
-O2 -lm |
|
对于C 语言 |
-O2 -lm |
-O2 -lm |
-O2 -lm |
|
对于Pascal语言 |
-O2 |
-O2 |
-O2 |
时间限制: 3000ms
空间限制: 256MB
来源: 浙江省选2016day1t1