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



可复制的 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