[ 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}$算法常數較小的版本:

[ Mersenne Twister ] 梅森旋轉算法

梅森旋轉算法是一種可以快速產生高級偽隨機數的算法，修正了很多以前的隨機速算法的缺陷(Ex:線性同於算法)。

這是專門用在蒙地卡羅測試用的，不要拿它來做持久化隨機二叉數的亂數產生器，會太慢

最為廣泛使用Mersenne Twister的一種變體是MT19937，可以產生32位整數序列，從C++11開始，C++也可以使用這種算法。在Boost C++,Glib和NAG數值庫中，作為插件提供。但是一般在競賽時可能會有不支援的情況發生，所以將它做成模板當作參考。

MT19937_64則是可以產生64位整數序列

以下提供模板:

[ chinese remainder theorem ] 中國剩餘定理

我是看維基百科實現的，所以就直接貼上模板
注意:

• crt函數的m[i]是模數
• crt函數的a[i]是原本數模m[i]後的值
• 必須要保證m兩兩互質
• 容易溢位

模板:

[ dynamic kd tree ] 動態kd樹模板

參考資料:

• k-d tree教學投影片
• http://andrewd.ces.clemson.edu/courses/cpsc805/references/nearest_search.pdf
• https://cw.fel.cvut.cz/wiki/_media/courses/a4m33pal/paska13.pdf
• 在二維空間的查找優化
• K-D Tree在信息学竞赛中的应用
• K-D tree的估价
• 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法 
• 感謝Morris大大的模板

kd樹的資料在網路上其實滿多的，但很多code效率不高或是功能不全，所以這邊稍微講解一下kd樹基本的一些操作

1. 構造
   現在有一個point序列S[0~n-1]，每個point都包含一個序列d[0~kd-1]表示維度，S[i].d[j]表示第i個點的第j維。
   節點的資料型別定義為node，裡面有l,r兩個指標分別指向左右兩顆子樹，還有一個point pid表示所存的point。
   構造的過程是一個遞迴結構，大致代碼如下:
   當前這個節點的k稱為分裂維度
   
2. 查找
   kd樹支援兩種查找法:
   一、給定一個點p和一個數字k，求離p前k近的點有哪些
   二、給定一個範圍，求範圍內有哪些點
   兩種方法跟一般爆搜有點像，但是利用了kd樹可以做到有效的剪枝，有時候可以判斷被切分出來的範圍內有沒有機會存在前k近點或是在範圍內，直接看模板應該就懂了
3. 刪除
   模板裡沒有附刪除的code所以會寫在這裡。
   首先如果找到要刪除的節點是葉節點直接刪除就好了；如果不是葉節點，假設現在這個點的分裂維度是k，就拿他右子樹第k維最小節點mi去替代他，接著遞迴刪除右子樹的mi；如果沒有右子樹，就拿他左子樹第k維最小節點mi去替代他，然後把左右子樹互換，接著遞迴刪除右子樹的mi。
   
   找到要刪除的點用查找中的第一種方法就好了，這裡p=要刪除的點，k=1，查找的時候順便維護最近節點其位置與其對p的距離，若最近距離!=0則刪除失敗。
   
   那對一個子樹找第k維最小節點呢?方法很簡單，也是遞迴定義的:
   首先如果當前節點o的分裂維度剛好是第k維，則若o有右子樹的話答案必在o的右子樹，否則答案為o，如果o的分裂維度!=k，則遞迴搜尋左右子樹，把得到的答案和o自己進行比較，求最小。
   接下來附上只有刪除操作的模板:
   
   

插入刪除通常配合替罪羊樹使用，插入很簡單模板有就不說了，接下來講一下複雜度:
設N=size(root)

• 構造:
  很明顯就是\(\ord{N \; log \; N}\)就不說了
• 查找:
  已經有人證明了，假設現在的維度有k維，則查找的最差複雜度是\(\ord{N^{1-1/k}}\)
  但是平均狀況下為\(\ord{log \; N}\)
• 插入:
  複雜度為\(\ord{樹的高度}\)，因為是套替罪羊樹，而且重構的時間是\(\ord{N \; log \; N}\)，所以單次插入的均攤時間複雜度是\(\ord{log \; N \; * \; log \; N}\)
• 刪除:
  有三個步驟需要分析，假設現在的維度有k維
  1. findmin:
     最多會遍歷\(\alpha^{(k-1)*(log_{\alpha}N)/k}=N^{1-1/k}\)個節點，所以是\(\ord{N^{1-1/k}}\)
     但實際操作量為\(N^{1-1/k}-n^{1-1/k}\)，n是最小值的子樹大小
  2. nearest:
     就是查找操作，所以是\(\ord{N^{1-1/k}}\)
     但因為是找相同點，可以優化code，所以實際操作量為\(N^{1-1/k}-n^{1-1/k}\)，n是相同點的子樹大小
  3. 刪除操作本身:
     看code明顯就是重複findmin直到把刪除的點變成葉節點為止，會感覺做了很多操作，但是我們發現把所有操作加起來後會=\(\ord{N^{1-1/k}}\)
     設\(o_1,o_2,...,o_d\)=findmin(root)找到的點,findmin(\(o_1\))找到的點,\(...\),要刪除的葉節點，\(n_1,n_2,...,n_d\)=findmin(root)找到的點的子樹大小,findmin(\(o_1\))找到的點的子樹大小,findmin(\(o_2\))找到的點的子樹大小,\(...\),要刪除的葉節點的子樹大小，\(d\)為樹的高度
     複雜度為:
     $$ N^{1-1/k}-n1^{1-1/k}+n1^{1-1/k}-n2^{1-1/k}+n2^{1-1/k}...-nd^{1-1/k}=\ord{N^{1-1/k}} $$

模板裡的code找的是曼哈頓距離，如果要找歐基里德距離只需要修改point裡的dist跟kd tree裡的heuristic即可，以下提供修改方法:
這樣查找時回傳的就是歐基里德距離的平方

以下附只有插入操作的模板:

以下附支援插入刪除的模板:
模板的使用方法請參考:

日月卦長的解題紀錄 [ IOICAMP2016 ] 動態曼哈頓最短距離

[ Miller-Rabin Strong Probable-prime Base ] 質數測試算法保證long long範圍內正確

這本來是隨機演算法，但是已經有一些人，找出一些特定底數，保證判定結果在某些範圍內正確。

如果是unsigned long long範圍內東西記得要用long long乘long long mod long long 的模板
這裡的範例已經加在code裡了，如果不需要可以把它拿掉(zerojudge a007不拿掉會變慢)

code:

[ Biconnected Component ] 雙連通分量(BCC)

一張無向圖上，不會產生割點的連通分量，稱作「雙連通分量」。一張無向圖的雙連通分量們，通常會互相重疊，重疊的部分都是原圖的割點。
可以利用堆疊+tarjan算法快速地找出那些點是割點和雙連通分量
以下提供模板: