drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ AOJ-ICPC400点 ICPC国内予選 グラフ マッチング 二部グラフ 二部マッチング フロー AOJ-ICPC けんちょん本演習問題 【問題集】フローの入門 割当問題 NoviSteps1D 典型的な二部マッチングの問題です。 問題へのリンク 問題概要 枚の赤いカードと、 枚の青いカードとの間でマッチングを作っていきます。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。 最大マッチングのサイズを求めてください。 考えたこと 二部グラフを作って、二部マッチングアルゴリズムで解くことができます。ここでは スーパー頂点 を追加して、最大流アルゴリズム Ford-Fulkerson 法のよる実装 二部マッチング専用の高速アルゴリズム Hopcroft-Karp 法による実装 を示します。 コード (Ford-Fulkerson 法による… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2021%2F08%2F05%2F175900" title="AOJ 1163 カードゲーム (ICPC 国内予選 2009 E) (1D, 400 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2021-08-05 17:59:00 rich https://drken1215.hatenablog.com/entry/2021/08/05/175900 1.0 100%