loj#P3642. 「2021 集训队互测」交朋友
「2021 集训队互测」交朋友
Cannot parse: undefinedms error parsing time
题目描述
这是一道提交答案题。
有 个人,在他们之间组织了若干次聚会。一开始任意两个人都不是朋友。在每一次聚会中,参加的人两两都会成为朋友。现在你忘记了一共组织了多少次聚会,也忘记了每次聚会有谁参加,只知道最后有哪些人成为了朋友。你想要还原出聚会的过程。显然聚会的方案不是唯一的,你想要找出一种使得聚会次数尽量少的方案。次数越少,得分越高,具体评分方式见评分标准。
输入格式
所有输入数据 friends1.in ~ friends10.in
见下发文件,分别对应 个测试数据。
每组数据中,第一行包含两个正整数 ,表示人数和朋友对数。
接下来 行,每行包含两个数 ,表示 和 这两个人是朋友。
输出格式
输出到 friends1.out ~ friends10.out
。
第一行一个正整数 ,表示你的方案中聚会的次数。
接下来 行,每行表示一次聚会。先输出一个数 ,表示这次聚会参加的人数。一行内紧接着包含 个互不相同的正整数,表示这次聚会参加的人的集合。
你需要保证这 个聚会组织后满足输入的 对人是朋友,且剩下的人之间没有成为朋友。
你还需要保证 且每次参加聚会的人数之和不超过 。
4 5
1 2
1 3
2 3
2 4
3 4
2
3 1 2 3
3 2 3 4
数据范围
测试点标号 | 特殊性质 | ||
---|---|---|---|
1 | |||
2 | |||
3 | 不存在 | A | |
4 | |||
5 | |||
6 | |||
7 | |||
8 | |||
9 | |||
10 |
特殊性质 A :可以把人分为两组,使得组内人与人之间都不是朋友。
如果 有值,那么说明这一个测试点中,数据以如下方式生成:对于每两个人 , 和 有 的概率是朋友,有 的概率不是朋友。
评分标准
如果你的输出不符合题目要求,那么得分为 。
如果你的输出是正确的,令 为你的方案中团的个数,对于这个测试点,你的得分以如下方式计算:
- 如果 ,得分为 。
- 如果 ,得分为 。
每个测试点的参数 和分数 如下:
测试点标号 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
在有 friends1.in ~ friends10.in
的文件夹中,将你的答案存在 friends1.out ~ friends10.out
后,你可以用下发文件中的 checker.cpp
来得知自己每个测试点的当前得分。