spfa的時間複雜度到底如何？
這幾天寫了兩道差分約束的題目。
一道是bzoj2330糖果。此題正常寫完後t掉了一個點。然後看了題解，發現連接超級源的時候從n到1可以秒過，一試從超時直接到90ms。
然後寫了bzoj1731排隊佈局。吸取經驗後超級源從n到1連邊，然後後三個點超時慘不忍睹。又看題解，改回從1到n連邊，秒過。
請問這種題目到底怎麼辦。玄學的spfa有什麼辦法可以拯救她嗎？
SPFA的複雜度是O(|V||E|)。
對於|V|,|E|在10^5級別的題目，正解肯定不是SPFA（不然就是錯題）。例如BZOJ2330正解是O(|V|+|E|)的縮強連通分量。至於SPFA換一種連邊順序能跑過去，不過是數據水而已。
瀉藥
如何卡spfa？?www.zhihu.com
請用這個演算法，對於隨機的差分約束系統時間複雜度是線性的，當然菊花圖另說；能卡掉NTR演算法的圖SPFA也過不去；要代碼的話私聊；此外這篇回答還分析了SPFA的時間複雜度。
spfa。。。很容易被卡
最壞複雜度O（VE）。
但是T主要原因就是因為這東西真是好卡。
看看隔壁dinic，複雜度比這個還差勁，但是就是卡不掉，每個題基本都是期望最優複雜度。因為你想讓這個題卡掉的話，題面就像是直接說出來卡你，那就沒啥意義了。
要是沒有堆優化的DJ我估計卡SPFA的人會幾乎銷聲匿跡。
複雜度玄學，救不了…
之前CF有道題就是卡SPFA的
推薦閱讀：
