← 返回题目列表

AtCoder · joisc2017_d

D. 安排门票

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

以下是来自日本的原始新闻PDF,已完整保存和染色。

切符の手配 (Arranging Tickets) - 原题 PDF 第 1 页
原题PDF第1页
切符の手配 (Arranging Tickets) - 原题 PDF 第 2 页
原题PDF第2页
切符の手配 (Arranging Tickets) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                 Contest Day 2 – Arranging Tickets


                切符の手配(Arranging Tickets)



  JOI 国にはN 個の駅1, 2, . . . , N がある.これらは,円形の線路に沿って時計回りに順に並んでいる.
 鉄道に乗るための切符はN 種類あり,それぞれ1, 2, . . . , N の番号が付けられている.切符i (1 ≦i ≦N −1)
を1 枚用いると,駅i から駅i + 1,または駅i + 1 から駅i へ1 人が移動できる.また,切符N を1 枚用い
ると,駅1 から駅N,または駅N から駅1 へ1 人が移動できる.これらの切符は,N 種類の切符をちょ
うど1 枚ずつ含むN 枚セットの形でのみ販売されている.
 あなたは,JOI 国の旅行会社で切符の手配をする業務を行っている.
 本日,あなたはM 件の依頼を受けた.i 番目(1 ≦i ≦M) の依頼は,駅Ai から駅Bi にCi 人が移動した
い,というものである.ただし,移動するCi 人は,全員が同じ経路で移動する必要はない.
 これらの依頼をすべて処理するために,切符を最小で何セット購入する必要があるかを求めたい.


課題

 駅の数および依頼の情報が与えられたとき,購入すべき切符のセット数の最小値を求めるプログラムを
作成せよ.


入力

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

   • 1 行目には,2 個の整数N, M が空白を区切りとして書かれている.これは,JOI 国にN 個の駅があ
   り,あなたがM 件の依頼を受けたことを表す.

   • 続くM 行のうちのi 行目(1 ≦i ≦M)には,3 個の整数Ai, Bi,Ci が空白を区切りとして書かれてい
   る.これは,i 番目の依頼が駅Ai から駅Bi にCi 人が移動したい,というものであることを表す.


出力

 標準出力に購入すべき切符のセット数の最小値を1 行で出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 3 ≦N ≦200 000.

   • 1 ≦M ≦100 000.



                     切符の手配– 1 / 3

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                 Contest Day 2 – Arranging Tickets


   • 1 ≦Ai ≦N (1 ≦i ≦M).

   • 1 ≦Bi ≦N (1 ≦i ≦M).

   • 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦M).

   • Ai , Bi (1 ≦i ≦M).


小課題

 この課題では小課題は全部で5 個ある.各小課題の配点および追加の制限は以下の通りである.

小課題1 [10 点]

   • N ≦20.

   • M ≦20.

   • Ci = 1 (1 ≦i ≦M).

小課題2 [35 点]

   • N ≦300.

   • M ≦300.

   • Ci = 1 (1 ≦i ≦M).

小課題3 [20 点]

   • N ≦3 000.

   • M ≦3 000.

   • Ci = 1 (1 ≦i ≦M).

小課題4 [20 点]

   • Ci = 1 (1 ≦i ≦M).

小課題5 [15 点]

 追加の制限はない.





                     切符の手配– 2 / 3

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                 Contest Day 2 – Arranging Tickets


入出力例

  入力例1        出力例1
   3 3                  1
   1 2 1
   2 3 1
   3 1 1

 全員が時計回りに移動すると,それぞれの切符は1 枚ずつ必要となるので,1 セット購入すればよい.



  入力例2        出力例2
   3 2                  3
   1 2 4
   1 2 2

 次のように移動することで,それぞれの切符は3 枚ずつ必要となる.

   • 最初の依頼において,3 人が時計回りに,1 人が反時計回りに移動する.

   • 2 番目の依頼において,2 人が反時計回りに移動する.

したがって,3 セット購入すればよい.
  2 セットで移動することはできないので,3 を出力する.



  入力例3        出力例3
   6 3                  2
   1 4 1
   2 5 1
   3 6 1

 例えば,切符を2 セット購入して,以下のように配ればよい.

   • 駅1 から駅4 に移動したい人に,切符1, 2, 3 を配る.

   • 駅2 から駅5 に移動したい人に,切符1, 6, 5 を配る.

   • 駅3 から駅6 に移動したい人に,切符3, 4, 5 を配る.

  1 セットで移動することはできないので,2 を出力する.





                     切符の手配– 3 / 3