[ Cocke-Younger-Kasami algorithm ] CYK算法

它是一個用來判定任意給定的字符串是否屬於某一個上下文無關文法的算法，還可以順便構造出二元語法樹和判斷是否有曖昧文法(Ambiguous Grammar)。對於一個任意給定的上下文無關文法，都可以使用CYK算法來計算上述問題，所以它是一個幾乎萬能的算法，但首先要將該文法轉換成喬姆斯基範式(CNF)。
這個算法主要是利用動態規劃的思想，給一個有$n$個字符的字符串s，和$R$條語法規則，則他的計算複雜度為$\ord{n^3R}$，空間複雜度為$\ord{n^2R}$。類似於optimal binary search tree的算法，對於每個s[l,r]我們去計算s[l,k]和s[k+1,r]能符合的所有規則。

我們用2016 NCPC的題目當例子
這裡給一個簡單的範例，給你一個語法規則如下 :
$
A \Longrightarrow AAAAAAA \qquad 20 \\
A \Longrightarrow AA \qquad 15 \\
A \Longrightarrow a \qquad 5
$
如果看不懂的，他大約的意思如下:
一個合法字串$A$可以是七個合法字串$A$所組成，也可以是兩個合法字串$A$所組成，也可以是小寫字母$a$所組成。
每個規則都給他一個權重，表示經過這個規則的轉換會有這些花費，我們會給一個目標字串，要找出把整個字串轉換成$A$的最小花費，例如給定字串$aaaaaaaa$，他的最小花費就是75。
這裡舉另一個例子:
$
A \Longrightarrow BA \qquad 10 \\
A \Longrightarrow bcd \qquad 5 \\
B \Longrightarrow c \qquad 4
$
給定字串$ccbcd$，他的最小花費就是33。
當然也會發生無法轉換的情況，這個時候叫要輸出$NIR$ 。

首先必須要把規則轉成喬姆斯基範式，這裡我以數字當作規則的名稱，當y=-1時表示這個cnf是s->x的規則，否則是s->xy的規則。
接著就可以跑我們的演算法啦:
當然它也可以用來判斷是不是有曖昧語法(ambiguous)，只要做一些小修改就行了

[ cantor expansion ] 康托展开

給一個$0 \sim n-1$共$n$個數字的全排列，求他是排名第幾的全排列；給一個名次，求全排列。這東西可以有效的減少hash_table的大小。
以下附上code:

使用前記得要呼叫init();

[ closest pair of points ] 平面上歐基里德距離最近點對

用分治法寫的，複雜度$\ord{n\log^2 n}$:

[ tree centroid ] 樹重心

一棵無向樹\(T=(V,E)\)，定義:
\(w_v(u)\)為點\(u\)的權重，\(u \in V\)
\(w_e(e)\)為邊\(e\)的權重，\(e \in E\)
\(d(u,v)\)為\(u\)到\(v\)路徑的權重和，\(u,v \in V\)

重心的定義是:
以這個點為根，那麼所有的子樹(不算整個樹自身)的大小都不超過整個樹大小的一半
即為最大的子樹最小的點

廣義的樹的重心:
無向樹\(T=(V,E)\)滿足
 \(w_v(u)≧0, \; \forall u \in V \)
 \(w_e(e)>0, \; \forall e \in E \)
設
\(c(u)=\sum_{v \in V}d(u,v)*w_v(v)\)
則樹重心 \(tree \; centroid=u \; | \; min(\{c(u):u \in V\})\)

在
 \(w_v(u)=1, \; \forall u \in V \)
 \(w_e(e)=1, \; \forall e \in E \)
的情況下，就是一般的樹重心

性質:

1. 把兩個樹通過一條邊相連得到一個新的樹，那麼新的樹的重心在連接原來兩個樹的重心的路徑上。
2. 把一個樹添加或刪除一個葉子，那麼它的重心最多只移動一條邊的距離。

用途:
樹分治、動態求樹重心等

可以利用DFS找出最大的子樹最小的點，即為樹重心
樹重心求法(用vector存無向樹):

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

[ Edmonds's general graph matching algorithm ] 一般圖最大匹配

關於匹配的教學我全部寫在這份投影片裡了:https://jacky860226.github.io/general-graph-weighted-match-slides/#/
所以這裡直接提供模板:
注意這裡必須要是無向圖

[ Kuhn-Munkres Algorithm ] 二分圖最大權完美匹配KM算法

關於此算法的介紹及教學請看這份投影片，這篇文章注重於討論$\ord{N^4}$的slack優化及$\ord{N^4}$到$\ord{N^3}$的過程。

在網路上曾經看到這段話:

"實際上KM算法的複雜度是可以做到$\ord{N^3}$的。我們給每個y頂點一個“鬆弛量”函數slack，
每次開始找增廣路時初始化為無窮大。在尋找增廣路的過程中，檢查邊(i,j)時，如果它不在相等子圖中，則讓slack[j]變成原值與lx[i]+ly[j]-w[i,j]的較小值。這樣，在修改頂標時，取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點：修 改頂標後，要把所有不在交錯樹中的Y頂點的slack值都減去d。"

這段話其實是錯的，請看底下的code:

$\ord{N^4}$常數優化版本
我們仔細看一下迴圈的層數。
第一層是一個for迴圈，執行N次；第二層有一個無線迴圈，但她最多執行N次；裡面有一個DFS，最多執行$\ord{N^2}$次，還有一些迴圈但是不影響複雜度所以不討論。
總複雜度是$\ord{N}*\ord{N}*\ord{N^2}$為$\ord{N^4}$，因此網路上大多數$\ord{N^3}$的code其實是錯的。

接下來看一下我修改後真正的$\ord{N^3}$code:
可以看到我在dfs裡面加了一個參數adjust，如果他是true，就跟原本的dfs沒兩樣，可以在找到增廣路後順便將增廣路擴充；如果他是false，整個dfs就變成只能判斷有沒有增廣路了。
主函數dfs的部分移到while的外面，而修改lx,ly和slack_y後的地方增加了一個迴圈來判斷這次的修改有沒有產生可行的增廣路，對於新增加的「等邊」，如果他有機會是增廣路的話，會對此「等邊」連像的點y進行dfs「判斷」有沒有增廣路(把adjust設成0)。如果有增廣路，就會跳出while，在進行一次dfs來擴充增廣路。
總複雜度是
$\ord{N}[第一層迴圈] * ( \ord{N^2}[dfs的時間] + \ord{N}[while的次數]*\ord{N} ) = \ord{N^3}$
這才是真正的$\ord{N^3}$算法，前者只是常數優化而已

最後是$\ord{N^3}$算法常數較小的版本: