QOJ.ac

QOJ

Total points: 100 Output Only

# 4905. 交朋友

Statistics

题目描述

这是一道提交答案题。

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

输入格式

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

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

接下来 $m$ 行,每行包含两个数 $x,y$ ,表示 $x$ 和 $y$ 这两个人是朋友。

输出格式

输出到 friends1.out ~ friends10.out

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

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

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

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

样例输入

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

样例输出

2
3 1 2 3
3 2 3 4

样例解释

一共有两次聚会。

第一次聚会中 $1,2,3$ 三个人参加,所以 $(1,2),(2,3),(1,3)$ 在聚会后成为了朋友。

第二次聚会中 $2,3,4$ 三个人参加,所以 $(2,3),(3,4),(2,4)$ 在聚会后成为了朋友。

在聚会完成后, $(1,2),(1,3),(2,3),(2,4),(3,4)$​ 成为了朋友,和输入相符合。

容易证明 $k$ 的最小值就是 $2$ ,所以样例输出为这组样例的最优解(但存在 $k$ 更大的合法方案)。

数据范围

测试点标号 $n=$ $p=$ 特殊性质
1 $6$ $\frac 12$
2 $10$ $\frac 12$
3 $50$ 不存在 A
4 $100$ $\frac 13$
5 $100$ $\frac 12$
6 $500$ $\frac 15$
7 $500$ $\frac 12$
8 $1000$ $\frac 15$
9 $1000$ $\frac 13$
10 $1000$ $\frac 12$

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

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

评分标准

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

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

  • 如果 $Z\leq Z_0$ ,得分为 $S$ 。
  • 如果 $Z>Z_0$ ,得分为 $S\times (\frac {Z_0}{Z})^3$ 。

每个测试点的参数 $Z_0$ 和分数 $S$ 如下:

测试点标号 $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$
$Z_0$ $4$ $9$ $ 321$ $288 $ $208 $ $3935 $ $2621 $ $12386$ $ 11198 $ $8486$
$S$ $4$ $8$ $6$ $9$ $9$ $11$ $11$ $13$ $13$ $16$

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

This is an output-only problem.

There are $n$ people, and several gatherings have been organized among them. Initially, no two people are friends. In each gathering, every pair of attendees becomes friends. Now, you have forgotten how many gatherings were held and who attended each gathering, but you remember which pairs of people ended up as friends. You want to reconstruct the process of the gatherings. Clearly, the solution is not unique, but you aim to find one that minimizes the number of gatherings. The fewer the gatherings, the higher the score, as detailed in the scoring criteria.

Input Format

All input data friends1.in ~ friends10.in are provided in the given files, corresponding to $10$ test cases.

For each dataset, the first line contains two positive integers $n$ and $m$, representing the number of people and the number of pairs of friends, respectively.

The following $m$ lines each contain two numbers $x$ and $y$, indicating that person $x$ and person $y$ are friends.

Output Format

Output your results to friends1.out ~ friends10.out.

The first line should contain a positive integer $k$, representing the number of gatherings in your solution.

The next $k$ lines should each represent a gathering. Each line should start with a number $r$, indicating the number of participants in the gathering. Then, $r$ distinct positive integers should follow, representing the set of people who attended the gathering.

You must ensure that after organizing these $k$ gatherings, the $m$ pairs of friends are satisfied, and that no additional people become friends.

You also need to ensure that $k \leq m$ and that the sum of the number of participants in all gatherings does not exceed $2m$.

Sample Input

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

Sample Output

2
3 1 2 3
3 2 3 4

Sample Explanation

There are two gatherings in total.

In the first gathering, persons $1$, $2$, and $3$ attended, so $(1,2)$, $(2,3)$, and $(1,3)$ became friends after the gathering.

In the second gathering, persons $2$, $3$, and $4$ attended, so $(2,3)$, $(3,4)$, and $(2,4)$ became friends after the gathering.

After the gatherings, $(1,2)$, $(1,3)$, $(2,3)$, $(2,4)$, and $(3,4)$ became friends, which matches the input.

It can be proven that the minimum value of $k$ is $2$, so the sample output is the optimal solution for this case (though other valid solutions with larger $k$ exist).

Data Range

Test Case $n=$ $p=$ Special Property
1 $6$ $\frac 12$
2 $10$ $\frac 12$
3 $50$ None A
4 $100$ $\frac 13$
5 $100$ $\frac 12$
6 $500$ $\frac 15$
7 $500$ $\frac 12$
8 $1000$ $\frac 15$
9 $1000$ $\frac 13$
10 $1000$ $\frac 12$

Special Property A: The people can be divided into two groups such that no one within the same group is friends with each other.

If $p$ has a value, it means that in this test case, the data was generated as follows: for every pair of people $i, j(i < j)$, $i$ and $j$ have a probability $p$ of being friends, and a probability $1-p$ of not being friends.

Scoring Criteria

If your output does not meet the problem's requirements, the score will be $0$.

If your output is correct, let $Z$ be the number of gatherings in your solution. For this test case, your score is calculated as follows:

  • If $Z \leq Z_0$, the score is $S$.
  • If $Z > Z_0$, the score is $S \times \left(\frac{Z_0}{Z}\right)^3$.

The parameters $Z_0$ and score $S$ for each test case are as follows:

Test Case 1 2 3 4 5 6 7 8 9 10
$Z_0$ $4$ $9$ $321$ $288$ $208$ $3935$ $2621$ $12386$ $11198$ $8486$
$S$ $4$ $8$ $6$ $9$ $9$ $11$ $11$ $13$ $13$ $16$

In the folder containing friends1.in ~ friends10.in, after storing your answers in friends1.out ~ friends10.out, you can use the provided checker.cpp file to check your current score for each test case.


or upload files one by one: