AGC028-C:Min Cost Cycle

問題

https://beta.atcoder.jp/contests/agc028/tasks/agc028_c

N 頂点の重み付き有向グラフが与えられる。各頂点に 2 つの整数が与えられており、A_i, B_i である。頂点 x から頂点 y への辺の重みは min(A_x, B_y) である。すべての頂点をちょうど 1 回通る有向サイクルの辺の重みの最小値を求めよ。

考え方

未知のものは、「すべての頂点をちょうど 1 回通る有向サイクルの辺の重みの最小値」である。A_i, B_i の辺の重みの小さいほうから N つの辺を選択して有向サイクルを構成したいが、有向サイクルを構成できない場合がある。有向サイクルを構成するための必要条件を整理しよう。

まずすべてが A_i, B_i の辺で構成することは明らかに可能である。そうでない場合について考えよう。

以下は有向辺について、from側の  A_i を使用する場合はオレンジ色、to側の B_i の辺を使用する場合は青色として有向サイクルを構成した例である。

f:id:d_tutuz:20181028202434p:plain

各頂点について、辺の割り当てを確認すると

  • パターンA:A_i, B_i の両方の辺が使われている
  • パターンB:A_i, B_i の両方の辺が使われていない
  • パターンC:A_i のみの辺が使われている
  • パターンD:B_i のみの辺が使われている

という 4 パターンに分類される。本例では以下のようになる。

パターン 頂点の集合
A \{1, 3\}
B \{2, 5\}
C \{4\}
D \{6\}

いくつか実験するとわかるが、パターンA を持たないと有向サイクルを構成することができないことがわかる。

よって必要条件は 「N つの辺を選択したときに同じ頂点となる辺が存在すること」となる。

あとはA_i, B_i の辺の重みでソートし小さいほうから N つの辺を選択する。必要条件を満たしていなければ満たすように辺を組み替えればよい。[1, N+2] の辺から N つ選べば鳩ノ巣原理より、必ず 2 つの辺を使う頂点が存在することがわかる。

Submission #3493586 - AtCoder Grand Contest 028

ポイント

  • 必要条件を整理する
  • 実験

類題