← 返回题目列表

AtCoder · joisc2007_fiber

fiber. 光纤(光纤)

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

光ファイバー (Fiber) - 原题 PDF 第 1 页
原题PDF第1页
光ファイバー (Fiber) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Fiber: 光ファイバー網の整備


input ファイル“fiber.in”
output 標準出力
ソースファイルfiber.c/fiber.cpp/Fiber.java
時間制限1 秒/ データ



 クロアチアでは国内の全ての都市を光ファイバー網で結ぶ計画が進行している.光ファイバー

を用いた通信回線は極めて高品質かつ高速であり,複数の都市を経由していても,ほとんど速
度が低下することなく,高速な通信を行うことができる.例えば,k 個の都市A1, . . . , Ak に対
し,都市Ai とAi+1  (1 ≦i ≦k −1) の間に光ファイバーが敷設されていれば,都市A1 とAk の

間で高速通信を行うことができる.

 クロアチア政府は,国全体に光ファイバー網を張り巡らせて,全ての都市と都市の間で高速

通信が行えるようにしたいと考えている.ところが困ったことに,現在では,規制緩和の影響

で複数の光ファイバー敷設業者が乱立しており,国全体の光ファイバー網がどうなっているの

か誰も把握していない.そこで,各業者から提出された光ファイバーの敷設情報を元に,全て

の都市と都市の間の高速通信を可能にするためには,あと何本の光ファイバーを新たに敷設す

る必要があるのかを調べることにした.

 光ファイバーの敷設情報が与えられたときに,全ての都市と都市の間で高速通信を可能にす

るために,あと何本の光ファイバーを新たに敷設する必要があるのかを求めるプログラムを作

成せよ.

Input. 入力ファイルfiber.in の1 行目には,クロアチア国内の都市の個数n (1 ≦n ≦10000)

が書かれている.各都市には1 からn までの番号が付けられている.2 行目には,敷設されて

いる光ファイバーの本数を表す整数m (1 ≦m ≦30000) が書かれている.続くm 行(3 行目~

m + 2 行目) は光ファイバーの敷設情報を表す.i + 2 行目(1 ≦i ≦m) には2 つの異なる整数
ai, bi (1 ≦ai, bi ≦n, ai ̸= bi) が空白を区切りとして書かれている.これは,都市ai と都市bi

の間に光ファイバーが敷設されていることを意味する.

Output. 出力は,標準出力に行うこと.全ての都市と都市の間で高速通信を可能にするため

に新たに敷設が必要な光ファイバーの本数の最小値を出力せよ.もし,現在のままでも全ての

都市と都市の間で高速通信が可能な場合は,0 を出力せよ.





                 光ファイバー網の整備–1/2

例
 fiber.in 標準出力
 8         2
 7
 3 5
 4 1
 5 4
 7 5
 4 7
 1 4
 6 8


 この入力例に対応する8 個の都市間の光ファイバー網を図示すると,以下の通りである.


                                    3
                                                         5

                          1                  4
                                    6

                          2
                                                 8
                                 7


  2 本の光ファイバーを新たに敷設すれば,全ての都市と都市の間で高速通信が可能になる.例

えば,都市2 と1,都市6 と4 の間に敷設すればよい.これが新たに必要な光ファイバーの本数

の最小値である.





                 光ファイバー網の整備–2/2