[ 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}}$的作法：
最近幫學長寫作業的時候，又發現了一個不需要多紀錄反邊的做法，但是每個點要同時記錄入邊和出邊，這樣可以用較少的記憶體完成演算法：

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

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

[ print itself ] 印出自己的code

一個會輸出自己的code:

可以看一下輸出:http://codepad.org/ZFGeRjkn

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

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