[ bipartite graph multiple matching ] 二分圖多重匹配增廣路算法

這種問題的題目通常是這樣:

給一張圖G有n1個點和n2個點，n1個點之間沒有邊，n2個點之間也沒有邊，但是n1和n2個點之間有m條邊(簡單的來說就是n1個點和n2個點的二分圖啦)，沒有重邊；其中n2個點每個點\(u\)都有一個可接受匹配數 \(c_u\)。
n1的點只能跟一個點匹配，但n2的點在不超過可接受匹配數的情況下，可以跟多個點匹配，求這張圖的最大匹配

通常可以利用拆點的方法或是flow來做，但是這樣空間跟效率都不是很好，這裡提供一個有效率的方法:

複雜度分析:
設n2個點每個點\(u\)都有一個值\(E_u\)表示和\(u\)相鄰的邊數，則總複雜度為
$$ \ord{n1*(\sum{c_u*E_u}+n1+n2)} $$

[ Augmenting Path Algorithm ] 二分圖匹配增廣路徑演算法

就是一直找增廣路徑，找到不能再找就是最大匹配惹
複雜度\(\ord{n1*(m+n2+n1)}\)，用dinic會比較快但是code比較長
模板:

[ Improved Shortest Augmenting Paths,ISAP ,Flow ] 網路流ISAP算法

使用gap優化(間隙優化)
使用當前弧優化

這裡提供遞迴與非遞迴兩種實現
基本上兩個版本效能差不多
遞迴版本:

非遞迴版本:

[ Dinic's algorithm ,Flow ] 網路流Dinic模板

使用當前弧優化

多路增廣模板:

單路增廣模板:

[ Edmonds–Karp algorithm ,Flow] 網路流Edmonds–Karp算法

這是最基本的多項式時間網路流演算法，因此在這裡我多了一些變化，首先是一般用鄰接矩陣，複雜度$\ord{\abs{V}^5}$的做法：
接著是使用鄰接串列，複雜度是$\ord{\abs{E}^2\abs{V}}$的作法：
最近幫學長寫作業的時候，又發現了一個不需要多紀錄反邊的做法，但是每個點要同時記錄入邊和出邊，這樣可以用較少的記憶體完成演算法：