3200. Six Degrees of Cowvin Bacon

单点时限: 1.0 sec

内存限制: 256 MB

The cows have been making movies lately, so they are ready to play a variant of the famous game “Six Degrees of Kevin Bacon”.

The game works like this: each cow is considered to be zero degrees of separation (degrees) away from herself. If two distinct cows have been in a movie together, each is considered to be one ‘degree’ away from the other. If a two cows have never worked together but have both worked with a third cow, they are considered to be two ‘degrees’ away from each other (counted as: one degree to the cow they’ve worked with and one more to the other cow). This scales to the general case.

The $N$ $(2 \leq N \leq 300)$ cows are interested in figuring out which cow has the smallest average degree of separation from all the other cows. excluding herself of course. The cows have made $M$ $(1 \leq M \leq 10000)$ movies and it is guaranteed that some relationship path exists between every pair of cows.


  • Line $1$: Two space-separated integers: $N$ and $M$
  • Lines $2$..$M+1$: Each input line contains a set of two or more space-separated integers that describes the cows appearing in a single movie. The first integer is the number of cows participating in the described movie, (e.g., $M_i$); the subsequent $M_i$ integers tell which cows were.


A single integer that is $100$ times the shortest mean degree of separation of any of the cows.


4 2
3 1 2 3
2 3 4


Cow 3 has worked with all the other cows and thus has degrees of separation: 1, 1, and 1 – a mean of 1.00 .

9 人解决,9 人已尝试。

13 份提交通过,共有 27 份提交。

5.0 EMB 奖励。

创建: 6 年,9 月前.

修改: 6 年,4 月前.

最后提交: 2 年,5 月前.

来源: USACO 2003 March Orange