#P3642. 「2021 集训队互测」交朋友

「2021 集训队互测」交朋友

Cannot parse: undefinedms error parsing time

题目描述

这是一道提交答案题。

nn​​ 个人,在他们之间组织了若干次聚会。一开始任意两个人都不是朋友。在每一次聚会中,参加的人两两都会成为朋友。现在你忘记了一共组织了多少次聚会,也忘记了每次聚会有谁参加,只知道最后有哪些人成为了朋友。你想要还原出聚会的过程。显然聚会的方案不是唯一的,你想要找出一种使得聚会次数尽量少的方案。次数越少,得分越高,具体评分方式见评分标准。

输入格式

所有输入数据 friends1.in ~ friends10.in 见下发文件,分别对应 1010​ 个测试数据。

每组数据中,第一行包含两个正整数 n,mn,m ,表示人数和朋友对数。

接下来 mm 行,每行包含两个数 x,yx,y ,表示 xxyy 这两个人是朋友。

输出格式

输出到 friends1.out ~ friends10.out

第一行一个正整数 kk ,表示你的方案中聚会的次数。

接下来 kk 行,每行表示一次聚会。先输出一个数 rr ,表示这次聚会参加的人数。一行内紧接着包含 rr 个互不相同的正整数,表示这次聚会参加的人的集合。

你需要保证这 kk 个聚会组织后满足输入的 mm 对人是朋友,且剩下的人之间没有成为朋友。

你还需要保证 kmk\leq m 且每次参加聚会的人数之和不超过 2m2m

4 5
1 2
1 3
2 3
2 4
3 4
2
3 1 2 3
3 2 3 4

数据范围

测试点标号 n=n= p=p= 特殊性质
1 66 12\frac 12
2 1010
3 5050 不存在 A
4 100100 13\frac 13
5 12\frac 12
6 500500 15\frac 15
7 12\frac 12
8 10001000 15\frac 15
9 13\frac 13
10 12\frac 12

特殊性质 A :可以把人分为两组,使得组内人与人之间都不是朋友。

如果 pp 有值,那么说明这一个测试点中,数据以如下方式生成:对于每两个人 i,j(i<j)i,j(i < j)iijjpp 的概率是朋友,有 1p1-p 的概率不是朋友。

评分标准

如果你的输出不符合题目要求,那么得分为 00

如果你的输出是正确的,令 ZZ 为你的方案中团的个数,对于这个测试点,你的得分以如下方式计算:

  • 如果 ZZ0Z\leq Z_0 ,得分为 SS
  • 如果 Z>Z0Z>Z_0 ,得分为 S×(Z0Z)3S\times (\frac {Z_0}{Z})^3

每个测试点的参数 Z0Z_0 和分数 SS 如下:

测试点标号 11 22 33 44 55 66 77 88 99 1010
Z0Z_0 44 99 321 321 288288 208208 39353935 26212621 1238612386 11198 11198 84868486
SS 44 88 66 99 99 1111 1111 1313 1313 1616

在有 friends1.in ~ friends10.in 的文件夹中,将你的答案存在 friends1.out ~ friends10.out 后,你可以用下发文件中的 checker.cpp 来得知自己每个测试点的当前得分。