AGC028-C:Min Cost Cycle
問題
https://beta.atcoder.jp/contests/agc028/tasks/agc028_c
頂点の重み付き有向グラフが与えられる。各頂点に つの整数が与えられており、 である。頂点 から頂点 への辺の重みは である。すべての頂点をちょうど 回通る有向サイクルの辺の重みの最小値を求めよ。
考え方
未知のものは、「すべての頂点をちょうど 回通る有向サイクルの辺の重みの最小値」である。 の辺の重みの小さいほうから つの辺を選択して有向サイクルを構成したいが、有向サイクルを構成できない場合がある。有向サイクルを構成するための必要条件を整理しよう。
まずすべてが の辺で構成することは明らかに可能である。そうでない場合について考えよう。
以下は有向辺について、from側の を使用する場合はオレンジ色、to側の の辺を使用する場合は青色として有向サイクルを構成した例である。
各頂点について、辺の割り当てを確認すると
- パターンA: の両方の辺が使われている
- パターンB: の両方の辺が使われていない
- パターンC: のみの辺が使われている
- パターンD: のみの辺が使われている
という パターンに分類される。本例では以下のようになる。
パターン | 頂点の集合 |
---|---|
A | |
B | |
C | |
D |
いくつか実験するとわかるが、パターンA を持たないと有向サイクルを構成することができないことがわかる。
よって必要条件は 「 つの辺を選択したときに同じ頂点となる辺が存在すること」となる。
あとは の辺の重みでソートし小さいほうから つの辺を選択する。必要条件を満たしていなければ満たすように辺を組み替えればよい。 の辺から つ選べば鳩ノ巣原理より、必ず つの辺を使う頂点が存在することがわかる。
Submission #3493586 - AtCoder Grand Contest 028
ポイント
- 必要条件を整理する
- 実験