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