NISHIO Hirokazu
[Translate]
最大二部マッチング
二部グラフ
の
最大マッチング
は
最大流
>
余談ですが、
最大二部マッチング
問題最速はこのアルゴリズムでした。
>
(クラスにDinicと名付けてますが、単なる互換性のためでDinic関係ないです。)
https://twitter.com/tomoyo_py/status/1279485648370462720?s=21
Tweet
Related Pages
二部グラフ
Dinic
最大流に帰着
AGC003B
ACLPC D
最大流
→
盲点カード
×
書いてから考えよう
×
自分を自分の一部に使う
×
回転の中心をずらす
×
イノベーション
×
シュンペーターによるイノベーションの定義
×
パルス幅変調
×
ファジー集合
×
円周率
×
ゼロによる位取り
×
確率共鳴
×
他に何かありますか?
×
そのxはどんな種類のxですか?
×
そのxは何のようですか?
×
そのxはどこにありますか?
×
身体感覚
×
メタファー
×
ジェスチャー
×
そのxはどこから来るのですか?
×
定数を関数で置き換える
×
変数を確率変数で置き換える
×
ユークリッド距離を一般の距離に
×
実数の離散化
×
捨てている次元を思い出す
×
四元数
×
曲がった空間を考える
×
1つでなければいけないのか?
×
対称性を追い求めてみる/捨ててみる
×
人に説明してみる
×
捨てているものを思い出す
×
双対を考える
×
記法を作る
×
名義尺度の扱い
×
探索範囲を狭める
×
平均に注意
×
0に近い値
×
オプションバリュー
×
絶対優位・比較優位
×
利用と探索のトレードオフ
×
データに置き換える
×
許可を求めるより謝罪
×
二部グラフ
×
平均だけでなく分布の形状に注意
×
知識の少ない人からでも学ぶことができる
×
囚人のジレンマ
×
全順序があるとは限らない
×
排中律
×
間違いを許容する
×
周波数領域
×
部分集合しか観測できない時、観測できなかったことに意味がある
×
平均からのズレとサンプルサイズ
×
距離は一種類ではない
×
最も効率的な工場は破綻する
×
百戦百勝は善の善なる者に非ず
×
形あるものは壊れるが速度に差がある
→
まだ絵のない盲点カード
→
最小カット
×
最大流
×
最小カットのカットは「辺を切る」ではない
×
LPとグラフと定式化
→
Project Selection Problem
→
2色で塗り分け→グラフのカット
×
グラフのカット
×
2色での塗り分け
×
最大カット→二部グラフなら片側を反転
×
最大カット
×
グリッドグラフ
×
二部グラフ
×
abc193
×
Project Selection Problem
→
✅ABC193F
→
貪欲法
×
独立性オラクル
×
pseudoforest
×
マトロイド交叉
×
2部グラフの最大マッチングは,分割マトロイド対のマトロイド交叉
×
最小費用流
×
増加道アルゴリズム
×
2部グラフ
×
最大マッチング
×
分割マトロイド
×
主双対アルゴリズム
×
primal-dual
→
マトロイド
→
オイラー路
×
グリッド上の幅優先探索
×
ハンガリアン法
×
二部グラフの最大マッチング
×
二重辺連結成分分解
×
二重頂点連結成分分解
×
全点対間最短路
×
単一始点最短路
×
強連結成分分解
×
彩色数
×
最大クリーク
×
最大流
×
最大独立集合
×
最小全域有向木
×
最小全域木
×
最小流量制限付き最大流
×
最小費用流
×
橋/関節点
×
bit
×
binary-trie
×
convex-hull-trick-add-monotone
×
li-chao-tree
×
link-cut木_部分木クエリ
×
link-cut木
×
ウェーブレット行列
×
スパーステーブル
×
スライド区間の昇順k個の和
×
セグメント木
×
トライ木
×
マージ可能ヒープ
×
列の平方分割
×
平衡二分探索木
×
永続配列
×
素集合データ構造
×
unionfind
×
ローリングハッシュ
×
接尾辞配列
×
最長共通接頭辞
×
最長回文
×
回文
×
複数文字列検索
×
hl分解
×
全方位木dp
×
最小共通祖先
×
木の直径
×
木の重心分解
×
根付き木に変換
×
mod-pow
×
オイラーのφ関数
×
オイラーのφ関数テーブル
×
ベル数
×
ラグランジュ補間
×
二項係数
×
二項係数テーブル
×
任意mod畳み込み
×
分割数
×
分割数テーブル
×
商列挙
×
形式的冪級数
×
形式的べき級数
×
拡張ユークリッドの互除法
×
拡張ユークリッド互除法
×
第2種スターリング数
×
約数列挙
×
素因数分解
×
素数テーブル
×
素数判定
×
組合せ
×
行列演算
×
進数変換
×
階乗
×
離散対数問題
×
高速フーリエ変換
×
divide-and-conquer-optimization
×
monotone-minima
×
スライド最小値
×
一次元累積和
×
二次元累積和
×
個数制限付きナップサック
×
最大長方形
×
最適二分探索木
×
最長増加部分列
×
ダブリング
×
包除原理
×
燃やす埋める問題
×
燃やす埋める
×
牛ゲー
×
mo’s_algorithm
×
offline-dynamic-connectivity
×
座標圧縮
×
アルゴリズム
→
Luzhiled's memo
→
アルゴリズム
×
蟻本
×
区間スケジューリング
×
二分探索木
×
unionfind
×
最短路問題
×
最小全域木
×
ユークリッドの互除法
×
ニ分探索
×
しゃくとり法
×
半分全列挙
×
座標圧縮
×
セグメント木
×
binary_lndexed_tree
×
バケット法
×
平方分割
×
ビットdp
×
bitdp
×
行列累乗
×
繰り返し二乗法
×
最大流
×
最小カット
×
二部マッチング
×
一般マッチング
×
マッチング
×
辺カバー
×
安定集合
×
点カバー
×
最小費用流
×
凸包
×
grundy数
×
強連結成分分解
×
2-sat
×
lca
×
ダブリング
×
接尾辞配列
×
sparse_table
×
rmq
×
atcoder
→
プログラミングコンテストチャレンジブック
→
最大マッチング
×
端から埋める
×
端の辺
×
m_solutions2019d
×
AGC029B
×
ドミノ倒し
×
貪欲法
→
グラフ上の最大マッチングを端から埋める
→
逆に大きい方から考える
×
グラフ上の最大マッチングを端から埋める
×
最大マッチング
→
AGC029B
→
木
×
二部グラフ
→
木は二部グラフ
→
atcoder
×
atcoder_library_practice_contest
×
numba
×
cython
×
フェニック木
×
セグメント木
×
遅延伝搬セグメント木
×
接尾辞配列
×
lcp_array
×
pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ
×
中国剰余定理
×
floor_sum
×
np.convolve
×
two_snuke
×
長整数が速い
×
dsu
×
unionfind
×
最大流
×
最小費用流
×
scc
×
2-sat
→
AtCoder Library
→
マトロイド
×
分割マトロイド
×
マトロイド交叉
×
増加道アルゴリズム
×
2部グラフ
×
最大マッチング
→
2部グラフの最大マッチングは,分割マトロイド対のマトロイド交叉
→
tokoharu
×
最短経路
×
差分制約
×
牛ゲー
×
最大流
×
最大流最小カット定理
×
最大循環流
×
最小費用流
×
最小費用循環流
×
Project Selection Problem
×
双対線形計画問題
→
LPとグラフと定式化
→
点カバー
×
最小点カバー
×
最大マッチング
→
安定集合
"
Engineer's way of creating knowledge
" the English version of my book is now available on
[Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from
[Scrapbox]
at
11/23/2025, 5:27:06 PM
[Edit]