2021-08-05から1日間の記事一覧
典型的な二部マッチングの問題です。 問題へのリンク 問題概要 枚の赤いカードと、 枚の青いカードとの間でマッチングを作っていきます。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。 最大マッチン…
AtCoder
AOJ
JAG
JAG模擬地区
AOJ-ICPC
AOJ-ICPC600点
フロー
グラフ
操作:辺の向きをflip
操作:flip
グラフのconnectivity
最適化テク:とりあえず元の問題の最適解を求める
最適解の数え上げ
BFS
けんちょん本演習問題
最適化テク:解に確実に含まれる要素を列挙する
DFS木やBFS木を考察する
思わず解きたくなる興味深い良問
【問題集】フローのステップアップ
ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね！！ 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…
AOJ
RUPC
最適化テク:自明な上界が最適解
フロー
グラフ
最短路問題
最小カット
最適化テク:解に確実に含まれる要素を列挙する
グラフの辺数を削減する
けんちょん本演習問題
Floyd-Warshall法
前処理
前処理:Floyd-Warshall法
DAG
【問題集】フローの入門
そのまま覚えたいシンプル設定の中堅以上の典型問題
グラフの辺数削減テク:ある最適解に含まれ得る辺以外を削除する
「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…
