# General Weighted Matching

### 参考文献リスト
文献
- http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf
- https://drive.google.com/file/d/1RD66csuDTAYXPmuCsiPi3HWBwtLg95T5/view
- https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides07.pdf

実装例
- https://judge.yosupo.jp/submission/81021
- https://networkx.org/documentation/stable/_modules/networkx/algorithms/matching.html#max_weight_matching
- https://jorisvr.nl/article/maximum-matching

### 変数一覧
- G:隣接行列(花と頂点のペアは具体的にどの辺を用いているかを保存)
- mate:マッチング相手
- p,z:頂点/花の双対変数
- flower:各花の頂点集合
- root:各花のroot(頂点/花)
- par:BFS木の親
- isS:0->unlabel,1->S,2->T
- slack:ラベルSの頂点/花への辺のうちslack変数が最小値をとるもの

### アルゴリズム詳細

- p(v)=inf,z(k)=0 に初期化,整数で処理するために重みを2倍にしておく
- マッチングしていない頂点からtightな辺を交互にたどってBFS
- tightかの判定:p(u)+p(v)=w(e)
- queueからの頂点は常にラベルSの頂点が入る
- 未知の頂点/花と接触したとき、そのマッチング相手をqueueに追加
- 接触時にparを更新する、同じ花に移動しない
- S-S間のtightな辺が現れたとき
- par,root,mateからLCAを求める
- 存在するなら圧縮して花にする(必ずラベルS)
- z(k)=0,u ~ lca,v ~ lcaのパスを復元して結合,rootを再帰的に変更
- しないならそれは増加パス パスを復元しながらマッチングを切り替える
- BFSで辿るところがない
- 双対変数をいじるための $\delta$ を求める
- $\delta_1,\delta_4$ : やるだけ
- $\delta_2,\delta_3$
- slackを用いて求める
- 各種操作でslackを更新する必要あり
- pが非正になったら終わり
- tightな辺が増えたとき : BFSのときと同じ
- ラベルTの花B_kがz[k]=0となったとき : 花を分解する
- 親と直接つながっている頂点とrootとのパスを交互道にして、他を孤立点にする