4
17
2015
0

POJ 2139 翻译

描述

奶牛们最近在拍电影,所以它们准备去玩著名游戏“Six Degrees of Kevin Bacon"的一种变体。

这个游戏是这样进行的:每只牛到自己的距离被视为0。如果两只不同的牛出现在同一部电影里,那么它们之间的距离被视为1。如果两只牛从来没有在同一部电影里工作过,但是它们都曾经和另外同一只牛分别在同一部电影里工作过,那么它们之间的距离被视为2(它们到那只一起工作过的牛的距离被视为1,然后到对方的距离又被视为1)。这个例子能扩展到其他的常规情况。

这N(2<=N<=300)头牛对计算出哪头牛到所有其他牛的平均距离(当然,不包括她自己)最小很感兴趣。牛们已经拍了M(1<=M<=10000)部电影,并且保证每两头牛之间都存在一定的关系。

输入格式

第1行:两个用空格隔开的数:N和M

第2行至第M+1行:每行输出包括若干个数,描述了出现在同一部电影里的奶牛。第一个数Mi描述了参与了这部电影的奶牛的数量,后面的Mi个数描述了是哪几头奶牛。

输出格式

仅一行:一个整数,表示所有奶牛中到其他奶牛的平均距离的最小值的100倍(向下取整)。

样例输入

4 2

3 1 2 3

2 3 4

样例输出

100

提示

奶牛3已经和其他的所有奶牛都合作过了并且因此和其他奶牛的距离都为1——平均值为1.00。

来源

USACO 2003 March Orange

PS:头一次翻译题目,可能翻译得不太好,语句可能不太通顺,凑合着看吧反正也就是一道水题

By WTRC

Category: POJ | Tags: POJ | Read Count: 266

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com