注: 解説放送や解説の証明の方針とは異なるかも知れません

補題

\(w\) の昇順に辺をグラフに追加していくことを考える。ここで、初めて \(A\), \(B\) 同士で連結となった頂点のペアが \((A_i, B_j)\) ならば、\(A_i\) と \(B_j\) でマッチングするような最適解が存在する。

補題の証明

最適解を1つ取る。もし、\(A_i\) と \(B_j\) がマッチングされていたら問題ない。

ここで、\(A_i\) と \(B_k\) が、及び \(A_l\) と \(B_j\) がマッチングされていたとする。マッチング相手をswapしても答えが悪化しない事、つまり、

\[ f(A_i, B_k) + f(A_l, B_j) \ge f(A_i, B_j) + f(A_l, B_k)...(1) \]

を示せば良い。ここで、仮定より

\[f(A_i, B_j) \le f(A_l, B_j), f(A_i, B_k), f(A_l, B_k)\]

が従う。

以後、\(A_i - B_j, A_l - B_j, A_i - B_k, A_l - B_k\) の4つの連結性だけを考えれば良い。特に、 \(A_i - B_j\) は最初に成立する。

まず、 \(f(A_l, B_j) \ge f(A_l, B_k)\)が成立する場合、仮定より直ちに \((1)\) が成立する。以後、 \(f(A_l, B_j) \le f(A_l, B_k)\) とする。よって、調べるべきは \(3\) 通りである。

\(f(A_l, B_j) \le f(A_i, B_k) \le f(A_l, B_k)\) の時

\(A_i - B_k\) の連結性が成立した時点で、 \(A_l - B_k\) の連結性も成立している（図を書くとわかりやすい）。つまり、 \(f(A_i, B_k) = f(A_l, B_k)\) である。 よって

\[ (1) ⇔ f(A_i, B_k) + f(A_l, B_k) \ge f(A_i, B_j) + f(A_l, B_k)\]

\[ ⇔ f(A_i, B_k) \ge f(A_i, B_j)\]

であり、これは仮定より成立。

\(f(A_l, B_j) \le f(A_l, B_k) \le f(A_i, B_k)\) の時

同様の整理の元、 \(f(A_l, B_k) = f(A_i, B_k)\) から \((1)\) 成立。

\(f(A_i, B_k) \le f(A_l, B_j) \le f(A_l, B_k)\) の時

同様の整理の元、 \(f(A_l, B_j) = f(A_l, B_k)\) から

\[ (1) ⇔ f(A_i, B_k) + f(A_l, B_k) \ge f(A_i, B_j) + f(A_l, B_k)\]

\[ ⇔ f(A_i, B_k) \ge f(A_i, B_j)\]

であり、これは仮定より成立。

よって、 \((1)\) が示され、補題は示された。

貪欲の証明

与えられた問題は次であった。

\((A_1, \dots, A_k)\) と \((B_1, \dots, B_k)\) が与えられた時、 \(\sum f(A_i, B_i)\)　が最小になるように \(B\) を並び替えよ。

ここで補題の手続きによって得られる\(a \in A\) と \(b \in B\) をマッチングさせる。すると、補題から示されたことより、残りの \((A_1, \dots, A_{k-1})\) と \((B_1, \dots, B_{k-1})\) に対し、\(\sum f(A_i, B_i)\)　が最小になるように \(B\) を並びかえれば最適解の \(1\) つを得る。

ここで、帰着後の問題が帰着前の問題とほとんど同じ形をしていることより、この手続きを繰り返すことにより最適解の \(1\) つを得る。

そして、解説の貪欲はこの手続きを行なっていると解釈できるので、貪欲の正当性が示された。