狠狠撸

第2回 ?早稲?田?大学プログラミングコンテスト

E: 独?立立記念念?日
keyword: グラフ、森、閉路路

问题概要

都市間にある道路路の様?子を表すグラフが与えられる。

问题概要

5 10

1

12 10 2 7

道路路には??長さが指定されている。

问题概要

5 10

1

12 10 2 7

道路路のうちいくつかを切切断して、都市を独?立立した k 個のグループに分ける。

问题概要

5 10

1

12 10 2 7

[!] 道路路の切切断には、??長さに応じたコストがかかる

问题概要

10

12 2 7

问题概要

ここでは、k = 3 つのグループに分割。
このときかかったコスト(切切断した道路路??長の合計)は、5 + 1 + 10 = 16

问题概要

Kグループに分割するときの、
最?小コストを求めてください。

ここでは、k = 3 つのグループに分割。
このときかかったコスト(切切断した道路路??長の合計)は、5 + 1 + 10 = 16

グラフの分割？ややこしそう???

グラフの分割？ややこしそう???
¤?? [!] グラフにはめちゃくちゃ厳しい条件がついている
¤?? 閉路路は?高々1つしかない

¤?? まず、閉路路がない場合を考えてみます。

部分点(30pt)制約
¤?? 制約
¤?? 都市の数 ?<= 100
¤?? 道路路の数 ?<= 10,000ぐらい
¤?? （これは実はこけおどし。実際はそんなに無い）
¤?? 閉路路は含まない

こんな感じのグラフになります

こんな感じのグラフになります

[!] つまり、森(:閉路路なし、連結とは限らない)になっている
(森: ?木が複数集まったグラフ。?木は閉路路を含まない、連結のグラフ)
上のグラフは?木が3つあり、森になっている

森だと何が嬉しい？

[!] どの道路路を切切ってもグループ数が 1 増える

部分点(30pts)解法
¤?? なので、k-(連結成分の個数) 回の切切断を?行行えばいい。
¤?? 切切断を?行行う道路路は、コストの?小さいものから貪欲に選んでよい
¤?? どれを切切ってもグループ数が増えるので

¤?? 解法
¤?? 連結成分（?木）を数える
¤?? その個数がK以上なら、切切る必要がない。
¤?? 辺をコストの昇順にソートする。
¤?? コストの?小さい?方から、連結成分がK個になるまで切切る。
¤?? そのときの合計が答えになる

満点制約
¤?? 制約
¤?? 都市の数 ?<= 100
¤?? 道路路の数 ?<= 10,000ぐらい
¤?? 閉路路は?高々1つ (0 or 1)

閉路路を?見見つける

[!] ?方法は後ほど解説します

閉路路の都市をまとめて考える

[!] これは森になっている

闭路路の1辺を消してみる

闭路路の1辺を消してみる

[!] やっぱりこれも森になっている
? さっきの部分点解法が使える

闭路路の?见见つけ?方

グラフに含まれる閉路路数が1の時に限り、
簡単な?方法が使えます

2

4 4

1 2 1 1

1 各頂点の次数（繋がってる辺の数）を
数えます。

2

4 4

1 2 1 1

1 次数1の頂点が含まれる辺を消します。
この時、両側の次数を1つずつ減らします

2

3 2

0 1 0 0

0 次数1の頂点が含まれる辺を消します。
この時、両側の次数を1つずつ減らします

2

3 2

0 1 0 0

0 同じ事を次数1の頂点がなくなるまで
繰り返します。

2

2 2

0 0 0 0

0 これ以上辺を消せないので終了了。
残った辺が閉路路になります。

解法
¤?? 連結成分を数える (その個数をAとおく)
¤?? A >= k なら 0 を出?力力して終了了

¤?? 閉路路を?見見つける

¤?? 場合分けをして、最?小コストを求める
¤?? 閉路路の道路路を切切断しない場合
¤?? 閉路路以外の道路路についてソートして、k-A個?足す
¤?? [!] 残りの道路路が?足りない場合に注意する
¤?? 閉路路の道路路を切切断する場合
¤?? 閉路路のうち、?一番短いのを消す。
¤?? 残った道路路をソートして k-A個?足す

統計
¤?? First AC : takapt (42:31)

¤?? 正解数 : 30
¤?? 通した?人(30/205) : 15%
¤?? ACだった解答(30/363) : 8%

狠狠撸

WUPC2nd E問題

More Related Content

WUPC2nd E問題