No.013 D

鉄塊を分割した結果, $(a_i, b_i)$ の重さに分割できて, $a_i$ を高橋君が, $b_i$ を青木君が使用するとする.

まず, 高橋君が使う分銅を揃えるために $a_i$ の種類数だけ鉄塊が必要がある.

次に青木君が使う分銅を揃えるために必要な鉄塊であるがまずは何も考えずに高橋君が使う分銅と同じ数だけ鉄塊を使ったとする. これが必要な鉄塊の最大値である.

しかし, 高橋君が使う分銅を作ったときに, 青木君が使う分銅も同時に作れたとしたら, その分は必要な鉄塊から除くことができる. この同時に作れる数の最大値が分かれば, 必要な鉄塊の最小値が分かる.

ということで, 二部グラフの最大マッチング問題に帰着させることができる.

$a_i, b_i$ をそれぞれ頂点とするグラフを作成し, 始点から $a_i$, $a_i$ から $b_i$, $b_i$ から終点へ容量1の辺を張り, 最大流を Ford-Fulkerson なりで解けばいい.