網絡流24題(二十一)

給定實直線 \(\mathbf{l}\) 上 \(n\) 個開區間組成的集合 \(\mathbf{i}\)，和一個正整數 \(k\)，試設計一個算法，從開區間集合 \(\mathbf{i}\) 中選取出開區間集合 \(\mathbf{s}\subseteq\mathbf{i}\)，使得在實直線 \(\mathbf{l}\) 上的任意一點 \(x\)，\(\mathbf{s}\) 中包含 \(x\) 的開區間個數不超過 \(k\)，且 \(\sum_{z\in\text{s}}\lvert z\rvert\) 達到最大（\(\lvert z\rvert\) 表示開區間 \(z\) 的長度）。

這樣的集合 \(\mathbf{s}\) 稱為開區間集合 \(\mathbf{i}\) 的最長 \(k\) 可重區間集。\(\sum_{z\in\text{s}}\lvert z\rvert\) 稱為最長 \(k\) 可重區間集的長度。

對于給定的開區間集合 \(\mathbf{i}\) 和正整數 \(k\)，計算開區間集合 \(\mathbf{i}\) 的最長 \(k\) 可重區間集的長度。

輸入的第一行有 2 個正整數 \(n\) 和 \(k\)，分别表示開區間的個數和開區間的可重疊數。接下來的 \(n\) 行，每行有 2 個整數，表示開區間的左右端點坐标 \(l,r\)，資料保證 \(l<r\)。

輸出最長 k 可重區間集的長度。

最大權不相交路徑、最大費用最大流

兩種思路：

第一種：

限制上限這種事情不難想到可以在源點或者彙點旁邊再連接配接一條流量上限為\(k\)的邊。

再繼續順着這個思路下去。我們需要把每一條邊的。

我們可以把每一個區間看作一個點，每一個點表示從\(a\)到\(b\)，假設區間之間有重疊那麼它們将會分流，而如果它們之間沒有重疊那麼說明他們可以共用同一流量。這就仿佛電路圖中的串聯與并聯一樣，我們把串聯的點連接配接在一起，而并聯的不管。

跑一下最大費用最大流即可。

第二種：

第一種方式的思考是把每一個區間都單獨的拎出來考慮他們之間的相交關系。而第二種方式則完全相反，我們把所有區間端點都壓在數軸上考慮。

想象一條從源點到終點的單向水流，這條水流相當于數軸，數軸上有很多點，那麼水流隻需要滿足一件事——流量小于等于\(k\)，就可以保證每一個點都不出現超過\(k\)次。

如果存在區間\((a,b)\)，那麼我們從\(a\)到\(b\)連接配接一條邊，容量為1，費用為區間長度。因為跑的是最大費用最大流，是以隻要它是合法的，它就會貪心的走向這條路。

兩種建圖方式。

方法1

按左端點排序所有區間，把每個區間拆分看做兩個頂點\(i，i+n\)，建立附加源\(s\)彙\(t\)，以及附加頂點\(s’\)。

連接配接\(s\)到\(s’\)一條容量為\(k\)，費用為0的有向邊。

從\(s’\)到每個\(i\)連接配接一條容量為1，費用為0的有向邊。

從每個\(i+n\)到\(t\)連接配接一條容量為1，費用為0的有向邊。

從每個頂點\(i\)到\(i+n\)連接配接一條容量為1，費用為負區間長度的有向邊。

對于每個區間\(a\)，與它右邊的不相交的所有區間\(b\)各連一條容量為1，費用為0的有向邊。

求最大費用最大流

方法2

離散化所有區間的端點，把每個端點看做一個頂點，建立附加源\(s\),彙\(t\)。

\(s\)為0，\(t\)為最右邊\(+1\)

從頂點\(i\)到頂點\(i+1\)，連接配接一條容量為\(k\)，費用為0的有向邊。

對于每個區間\([l,r]\)，從\(l\)對應的頂點\(i\)到\(r\)對應的頂點\(j\)連接配接一條容量為\(1\)，費用為負區間長度的有向邊。

求最大費用最大流，最大費用流值就是最長k可重區間集的長度。

具體建圖就會發現，後一種模型的邊數更少，第一種上線是\(o(n^2)\)，而後一種是\(o(n)\)