← 返回题目列表

AtCoder · joisc2010_regions

regions. 地区

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

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

地域 (Regions) - 原题 PDF 第 1 页
原题PDF第5页
地域 (Regions) - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                           Contest day 2 - Regions

                         地域(Regions)


  JOI 国にはN 個の都市があり,1 からN の番号がついている.これらの都市は,双方向に通行可能な道
でツリー状に接続されている.すなわち,任意の2 つの都市は道をたどって行き来が可能であり,かつそ
の経路は一意である.このとき,道はN −1 本である.
 都市を,M 個の地域に分けることにした.全ての地域は1 つ以上の都市を含み,全ての都市はちょうど
1 つの地域に含まれるようにしなければならない.また,同じ地域に含まれる任意の2 つの都市は,その
地域に含まれない都市を通らずに道をたどって行き来が可能でなければならない.
 各地域の直径の最大値dmax ができるだけ小さくなるように地域分けをしたい.ある地域の直径とは,そ
の地域に含まれる2 つの都市間の距離の最大値である.2 つの都市間の距離とは,2 つの都市を結ぶ経路に
含まれる道路の長さの和である.地域に1 つしか都市が含まれない時,その地域の直径は0 とする.

課題(TASK)

 道の情報と地域の数が与えられると,dmax の最小値を計算するプログラムを作成せよ.

制限(CONSTRAINTS)
   2 ≦N ≦30, 000 都市の数
   2 ≦M ≦N   地域の数
   1 ≦Ai < Bi ≦N  道i の結ぶ2 つの都市
   1 ≦Ci ≦100   道i の長さ

入力(INPUT)

 標準入力から以下の入力を読み込め.

   • 1 行目には整数N, M が空白を区切りとして書かれている.

   • 続くN −1 行には,1 行につき1 つの道について記述している.これらの行のうちのi 行目は道i に
   ついて記述しており,整数Ai, Bi,Ci が空白を区切りとして書かれている.

出力(OUTPUT)
 標準出力にdmax の最小値を表す1 つの整数を出力せよ.





                                                                                    Page 1 of 2

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                           Contest day 2 - Regions

採点基準(GRADING)
  20 点分のテストグループにおいて,M = 2, N ≦1, 000 である.
  40 点分のテストグループにおいて,M = 2 である.

入出力例(EXAMPLE)
  入力例(Sample Input)  出力例(Sample Output)
   5 2                 3
   1 4 2
   2 3 3
   2 4 1
   4 5 1

  2 つの地域を都市1, 4, 5 と都市2, 3 というようにすれば,dmax を3 にでき,これが最適である.

  入力例(Sample Input)  出力例(Sample Output)
   5 3                 2
   1 4 2
   2 3 3
   2 4 1
   4 5 1

  3 つの地域を都市1 と都市2, 4, 5 と都市3 というようにすれば,dmax を2 にでき,これが最適である.





                                                                                    Page 2 of 2