\( \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"}} \)

2015年10月14日 星期三

[ 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算法

直接提供模板:

[ Travelling Salesman Problem, TSP ] 旅行推銷員問題

假設圖是完全圖的情況下,從原點出發經過所有點一次並回到原點的最短路徑問題
以下為模板:

2015年10月6日 星期二

[ Rabin-Karp rolling hash ] Rabin-Karp 字串hash演算法

Michael O. Rabin和Richard M. Karp在1987年提出一個想法,即可以對模式串進行哈希運算並將其哈希值與文本中子串的哈希值進行比對。
設字串陣列為\(s[N]\),字元編號為\(0\)到\(N-1\)
首先建立陣列\(h[N+1]\),\(h[i]\)表示
\((s[0]*p^{i-1}+s[1]*p^{i-2}+...+s[i-1])\%M,h[0]=0\),其中\(p\)跟\(M\)是質數
假設要區編號\(L\)到編號\(R\)閉區間的hash值,則其為\((h[R+1]-h[L]*p^{R-L+1}\%M+M)\%M\)
如果要用double hash則用不同質數計算兩種不同的hash值,用pair拼起來即可
以下提供模板: