PKU3680 Intervals

如此這般，開始寫中文。
以後頹題難題只要解了就寫。

先說這道題，大意就是給定一堆Open Intervals，要保証選取某些Intervals使實數軸上的數字不會被覆蓋超過次，並且把選取的Intervals的獲利總數最大化。

好的，看起來很複雜對吧？不難發現用任何DP方法都應該得不到正確的結果。於是我們從題意直接著手。就取Sample最後一例說明吧。
把Intervals(不按比例)畫出來會成這個樣子﹕

1: |-----------------------------------------|
2: |--------------|
3: 　　　|---------------|
----------------------------------------------
　1　　100　　150　200　　　　　　10萬

假設第i區間取次Xi，從Sample我們可得X1, X2, X3。
把Intervals作離散化，可以得到以下4道不等式。同色Intervals代表屬同一不等式。
X1 + X2 <= K .....(1)
X1 + X2 + X3 <= K .....(2)
X1 + X3 <= K ..... (3)
X1 <= K ..... (4)
一般來說處理不等式都不好辦，我們嘗試引入鬆弛量(不是熊) Slack Variables，讓不等試變等式。
X1 + X2 + Y1 = K .....(1)
X1 + X2 + X3 + Y2 = K .....(2)
X1 + X3 + Y3 = K ..... (3)
X1 + Y4 = K ..... (4)
若果讓第i式與第i+1式相減(不包括i = 4)，按植樹原理可以得3式﹕
(2) - (1): X3 + Y2 = Y1
(3) - (2): Y3 = X2 + Y2
(4) - (3): Y4 = X3 + Y3
補上(1)及(4)，可得以下5式﹕
X1 + X2 + Y1 = K
X3 + Y2 = Y1
Y3 = X2 + Y2
Y4 = X3 + Y3
K = X1 + Y4 (我把這式倒轉了)
你可以發現，左式相加，就是右式，恰好得到了F=F這個結論。 我們再想深一層，如果套用 F_in = F_out，就是網絡流的守衡定律﹗(Flow Conservation) 若左式是代表入流量，右式便正好了是代表出流量。式子間的關係就可以靠變量來連繫了(比如出流式3聯繫了入流式2)。由此我們可以看式子就是點，變數就是 邊。假如變數X在第i式是出流，在第j式是入流，圖裡便有一條邊 i---->j。相通了這相的東西後，你可以利用變數Xi和Yi來構出一張圖。不過你會發現一件事﹕

(1) Constant怎樣處理？
(2) Source和Sink在哪？

想到這裡，你便猜到Constant的出入流正是對應Source和Sink。
好了。圖是出來了。問題是網絡中的Capacity到底是怎樣？
我們可以這樣分類﹕
Xi: 它代表選或不選第i個interval，故此Capacity頂多是1。
Yi: 它是調節不等式的變數，其值有修正不等式作用，故Capacity可取任意 (即無限)。
常數﹕就是Source / Sink的Capacity。

因 為這題不是要我們選最多的Intervals，而是把獲利最大化，我們便要考慮最小費用流(Min Cost Flow)。費用從何而定？當然費用就是選取Xi與否。故代表Xi的費用就是-Ci，基於最小費用流下我們可以得最小的負數費用(最後把它再負一次便 成)。最後構圖如下﹕

顯然易見，費用流得出最小費用為-100301，取絕對值便是答案。

問題來了﹕構圖不易。

留意以下觀察。
(1) 不失一般性，假設第i個interval的超始點必不多於第i+1個。構建式子時，若第P式開始出現變量Xi，Xi最後出現在式子Q，肯定Xi不會無故於P至Q式之間消失。因為Interval是連續嘛…
(2) 利用兩連續式相減，P式子減去P-1式子時必然利剩下Xi在左式(這不用証明吧…)。當Q+1式減Q式時，該式子的右邊必然出現Xi(取同樣道理)。至此 若果完全明白的話，你會明白為何第1式必須留下，原因是第一式首次出現的變數沒有上一式可以減，反而式子本身就有它們在了。而最後一式最倒轉也是基於這個 原理。
(3) 假設有N等式。經此構造會有 N-1 兩兩相減式 + 2 首尾式 = N+1 式。其中如果第i式左邊出現Yi，右式因為相減下令Yi出現在第i+1式的右邊。

由此得知，若Xi出現在式子P至Q之間，肯定得出邊 (Q+1)-->P。亦可以發現Source必須接N+1式，1式必須接Sink。因此無需處理複雜式子間關係才能構圖。

問題又來了﹕如何得知式子數？
這 問題是對離散化不熟悉的人最常見的(我也是)。一般構建方法可以記錄Intervals的Start及End，對應+1或-1然後便知變數屬甚麼範圍的式 子。此方正確但難以處理區間邊緣重疊的問題，容易出錯。我的做法是把所有Intervals的起點終點的**唯一數字**排序，那麼這個數字的次序便對應 起點的出現在甚麼式子的左邊，和終結時變數應該會在甚麼式子的右式出現。再以Sample為例，可以如下數字﹕
次序 | 1　2　3　　4　　5
數字 | 1 100 150 200 100000
取第二Interval為例，X2出現在第1式的左邊和第3式的右邊，故此得出3-->1的邊。

知道這個便是貼模版的時候。你會發覺不對勁﹕負邊用Bellman-Ford會否出現Negative Cycle?答案是否定的。Negative Cycle不會出現在這種構圖中，你可以再慢慢証明。然而當你放心貼上Bellman-Ford的時候，會發現PKU上會說TLE…因此，你可以嘗試用用 SPFA(Shortest Path Faster Algorithm)。然後，又是超時。原因是，SPFA對層圖處理比較慢，所以要加上優化。只要加上SLF(Shortest Label First)即可以極速AC。再加上LLL(Largest Label Last)只是錦上添花，想嘗試寫寫亦無傷大雅。