4
17
2015
1

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: 523
boardmodelpaper.com 说:
Jan 08, 2024 06:13:33 PM

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


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