最小重み辺被覆を最小重み完全マッチングに帰着します．

入力 \(2\) 部グラフを \(G = (U, W; E)\) として，辺重みを \(w \colon E \to \mathbb{Z}_{\ge 0}\) とします． このとき，\(G\) の辺被覆の \(w\) に関する最小重みは，以下のように構成した \(2\) 部グラフ \(\tilde{G} = (\tilde{U}, \tilde{W}; \tilde{E})\) の完全マッチングの \(\tilde{w} \colon \tilde{E} \to \mathbb{Z}_{\ge 0}\) に関する最小重みのちょうど半分に等しくなります． 構成方法を書いてから正当性を説明しますが，直観的には「最小重み完全マッチングで被覆することを目指して，余った頂点は接続する辺のうち最も軽いものを追加することで補う」という気持ちです．

頂点集合に関して，\(U',W'\) をそれぞれ \(U,W\) のコピーとして，\(\tilde{U} = U \cup W',~\tilde{W} = W \cup U'\) とします． 辺集合に関して，\(E'\) を \(E\) のコピー（ \(U',W'\) 間を \(U,W\) 間と同様に結ぶ），\(E'' = \{\, \{v, v'\} \mid v' \in U' \cup W'~は~v \in U \cup W~のコピー \,\}\) として，\(\tilde{E} = E \cup E' \cup E''\) とします． 最後に，重み \(\tilde{w}\) に関して，\(E \cup E'\) の辺についてはオリジナルの辺の \(w\) 重みと同じとし，\(E''\) の辺 \(\{v, v'\}\) については，\(G\) で \(v \in U \cup W\) に接続する辺の \(w\) 重みの最小値の \(2\) 倍とします．（接続する最も軽い辺をオリジナルとコピーで \(2\) 回使うという気持ちです．）

まず，\(\tilde{G}\) の任意の最小重み完全マッチング \(\tilde{M}\) に対し，\(G\) の辺被覆であって重みがちょうど半分となるものが存在します． \(\tilde{M} \cap E''\) の辺を両端点と接続辺もろとも取り除くと，残りの部分は \(G\) 由来の部分とそのコピーとなり，それぞれで取っている完全マッチングの重みは同じとなります．（そうでなければ，重い方を軽い方のコピーに置き換えた方が得であり，\(\tilde{M}\) の重み最小性に矛盾します．） したがって，\(G\) 側で残された完全マッチングに，\(\tilde{M} \cap E''\) でマッチされていた各頂点 \(v \in U \cup W\) に接続する辺のうち最も軽いものを追加することで，\(G\) の辺被覆であって重みが \(\tilde{w}(\tilde{M})\) のちょうど半分であるものを構成できます．

逆に，\(G\) の任意の最小重み辺被覆 \(C\) に対し，\(\tilde{G}\) の完全マッチングであって重みがちょうど \(2\) 倍となるものが存在します． \(C\) の中で極大なマッチングを任意に取って \(M\) とします． このとき，\(M\) でマッチされていない頂点 \(v\) に接続する辺で \(C\) に含まれるものは，\(v\) に接続するすべての辺の中で最も軽いもの \(1\) 本だとしてよいです．（ \(M\) の極大性から \(v\) の相手は \(M\) でマッチ済みであり，重み \(w\) は非負なので \(2\) 本以上取って得をすることはありません．また，最も軽い辺でなければ最も軽い辺に取り換えた方が得です．） したがって，\(M\) とそのコピー \(M'\) に，\(M\) でマッチされていない各頂点 \(v\) に関して \(\{v, v'\} \in E''\) を加えることで，\(\tilde{G}\) の完全マッチングであって重みが \(w(F)\) のちょうど \(2\) 倍となるものが構成できます．

以上より，\(G\) の辺被覆の \(w\) に関する最小重みが，\(\tilde{G}\) の完全マッチングの \(\tilde{w}\) に関する最小重みのちょうど半分となることが証明できました．

実装例 (C, 537 ms)