← 返回题目列表

AtCoder · joisc2019_g

G. 指定城市

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

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

指定都市 (Designated Cities) - 原题 PDF 第 1 页
原题PDF第1页
指定都市 (Designated Cities) - 原题 PDF 第 2 页
原题PDF第2页
指定都市 (Designated Cities) - 原题 PDF 第 3 页
原题PDF第3页
指定都市 (Designated Cities) - 原题 PDF 第 4 页
原题PDF第4页
指定都市 (Designated Cities) - 原题 PDF 第 5 页
原题PDF第5页
可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                Contest Day 3 – Designated Cities

                指定都市(Designated Cities)



  JOI 国にはN 個の都市があり,1 からN までの番号が付いている.これらの都市は,1 からN −1 までの
番号が付いたN −1 本の道路で結ばれている.道路i (1 ≦i ≦N −1) は都市Ai と都市Bi を結んでいる対向
2 車線の道路である.道路i は,都市Ai から都市Bi へ向かう車線と,都市Bi から都市Ai へ向かう車線か

らなる.どの都市からどの都市へも何本かの道路を通行することで移動できる.

 現在,どの道路のどの車線も,整備されていない状態である.それぞれの道路のそれぞれの車線につい

て,その車線を整備するのに必要なコストが分かっている.道路i (1 ≦i ≦N −1) の,都市Ai から都市Bi
へ向かう車線を整備するのに必要なコストはCi であり,都市Bi から都市Ai へ向かう車線を整備するのに
必要なコストはDi である.
  JOI 国の大臣であるK 理事長は,いくつかの都市を特別観光都市として指定することができる.都市x

(1 ≦x ≦N) を特別観光都市に指定すると,すべての道路i (1 ≦i ≦N −1) に対して,次のことが起こる:

    道路i が直接結ぶ2 つの都市のうち,都市x に近い方をa,遠い方をb とおく.なお,都市x に近い

   方の都市とは,x に到達するために通る必要のある道路の本数が少ない方の都市を指す.このとき,

   都市b から都市a へ向かう車線が(まだ整備されていないなら) 整備される.

 特別観光都市を指定することによって整備される車線は,税金で整備される.しかし,特別観光都市の指

定をすべて終えたあと,まだ整備されていないままになっているすべての車線を,K 理事長のポケットマ

ネーで整備する必要がある.

 K 理事長に対しQ 個の計画が提案された.j 番目(1 ≦j ≦Q) の計画においては,特別観光都市が1 つも
指定されておらず,かつ,どの道路のどの車線も整備されていない状態から始めて,ちょうどE j 個の都市
を選び特別観光都市に指定する.K 理事長は,各計画について,ポケットマネーで整備する必要のある車線

の整備コストの合計の最小値を知りたい.

  JOI 国の都市の個数,道路の情報,計画の情報が与えられたとき,各計画について,ポケットマネーで整

備する必要のある車線の整備コストの合計の最小値を求めるプログラムを作成せよ.





                       指定都市– 1 / 5

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                Contest Day 3 – Designated Cities



入力


 入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.


    N

      A1 B1 C1 D1
                                 ...

      AN−1 BN−1 CN−1 DN−1

    Q

      E1
                                 ...

     EQ


出力

 標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には,j 番目の計画について,ポケットマネーで整備す

る必要のある車線の整備コストの合計の最小値を出力せよ.


制約

    • 2 ≦N ≦200 000.
    • 1 ≦Ai ≦N (1 ≦i ≦N −1).
    • 1 ≦Bi ≦N (1 ≦i ≦N −1).
    • Ai , Bi (1 ≦i ≦N −1).
    • どの都市からどの都市へも何本かの道路を通行することで移動できる.

    • 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦N −1).
    • 1 ≦Di ≦1 000 000 000 (1 ≦i ≦N −1).
    • 1 ≦Q ≦N.
    • 1 ≦E j ≦N (1 ≦j ≦Q).





                       指定都市– 2 / 5

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                Contest Day 3 – Designated Cities



小課題

    1. (6 点) N ≦16.
    2. (7 点) Q = 1,E1 = 1.
    3. (9 点) Q = 1,E1 = 2.
    4. (17 点) N ≦2 000.

    5. (17 点) Q = 1.

    6. (44 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   4                              9

   1 2 1 2                        1

   1 3 3 4

   1 4 5 6

   2

   1

   2

 ちょうど1 個の都市を特別観光都市に指定することを考える.都市1 を特別観光都市に指定すると,道

路1 の都市2 から都市1 へ向かう車線,道路2 の都市3 から都市1 へ向かう車線,そして道路3 の都市4

から都市1 へ向かう車線が整備される.このとき整備されずに残るのは,道路1 の都市1 から都市2 へ向

かう車線,道路2 の都市1 から都市3 へ向かう車線,そして道路3 の都市1 から都市4 へ向かう車線であ

る.これらの車線の整備コストの合計は,1 + 3 + 5 = 9 である.ちょうど1 個の都市を特別観光都市に指定

する場合,整備されずに残る車線の整備コストの合計をこれより小さくすることはできない.よって答えは

9 になる.

 ちょうど2 個の都市を特別観光都市に指定することを考える.都市3, 4 を特別観光都市に指定すると,整

備されずに残るのは,道路1 の都市1 から都市2 へ向かう車線である.この車線の整備コストは1 である.

ちょうど2 個の都市を特別観光都市に指定する場合,整備されずに残る車線の整備コストの合計をこれより

小さくすることはできない.よって答えは1 になる.





                       指定都市– 3 / 5

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                       Spring Training Camp/Qualifying Trial

                                           March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                              Contest Day 3 – Designated Cities


 入力例2              出力例2

 5                              36

 1 3 13 6

 5 1 17 8

 5 2 6 10

 1 4 16 11

 1

 1

この入力例は小課題2 の制約を満たす.



 入力例3              出力例3

 6                              14

 1 6 6 12

 6 2 5 16

 1 4 13 4

 5 1 19 3

 3 1 9 13

 1

 2

この入力例は小課題3 の制約を満たす.





                      指定都市– 4 / 5

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                      Spring Training Camp/Qualifying Trial

                                          March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                             Contest Day 3 – Designated Cities


入力例4                             出力例4

15                                                      44

14 5 12 7                                               12

14 12 6 5                                               6

14 10 14 16

9 14 16 12

13 7 4 15

1 3 8 1

6 7 15 13

15 4 4 6

9 1 12 6

13 1 7 6

13 4 5 15

2 6 11 19

8 4 12 7

13 11 14 5

3

3

6

7





                     指定都市– 5 / 5