\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年8月5日 星期五

[ 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)} $$

沒有留言:

張貼留言