網絡流24題21. 最長 k 可重區間集問題

2019-11-06 06:03:28

字體：大中小

來源：轉載

供稿：網友

最長 k 可重區間集問題

Description

給定實直線 L 上 n 個開區間組成的集合 I，和一個正整數 k，試設計一個算法，從開區間集合 I 中選取出開區間集合 S?I，使得在實直線 L 的任何一點 x，S 中包含點 x 的開區間個數不超過 k，且 Σ|z|，z∈s $/Sigma |z|，z∈s$ 達到最大。這樣的集合 S 稱為開區間集合 I 的最長 k 可重區間集。Σ|z|，z∈s $/Sigma |z|，z∈s$ 稱為最長 k 可重區間集的長度。對于給定的開區間集合 I 和正整數 k，計算開區間集合 I 的最長 k 可重區間集的長度。

Input

第 1 行有 2 個正整數 n 和 k，分別表示開區間的個數和開區間的可重迭數。接下來的 n 行，每行有 2 個整數，表示開區間的左右端點坐標。

Output

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

Sample Input

4 2 1 7 6 8 7 10 9 13

Sample Output

題解

搬運的題解，不得不說方法二太巧妙了。。

【問題分析】

最大權不相交路徑問題，可以用最大費用最大流解決。

【建模方法】

方法1

按左端點排序所有區間，把每個區間拆分看做兩個頂點<i.a> $<i.a>$ <i.b> $<i.b>$ ，建立附加源S匯T，以及附加頂點S’。

1、連接S到S’一條容量為K，費用為0的有向邊。 2、從S’到每個<i.a> $<i.a>$ 連接一條容量為1，費用為0的有向邊。 3、從每個<i.b> $<i.b>$ 到T連接一條容量為1，費用為0的有向邊。 4、從每個頂點<i.a> $<i.a>$ 到<i.b> $<i.b>$ 連接一條容量為1，費用為區間長度的有向邊。 5、對于每個區間i，與它右邊的不相交的所有區間j各連一條容量為1，費用為0的有向邊。

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

方法2

離散化所有區間的端點，把每個端點看做一個頂點，建立附加源S匯T。

1、從S到頂點1（最左邊頂點）連接一條容量為K，費用為0的有向邊。 2、從頂點2N（最右邊頂點）到T連接一條容量為K，費用為0的有向邊。 3、從頂點i到頂點i+1(i+1<=2N)，連接一條容量為無窮大，費用為0的有向邊。 4、對于每個區間[a,b]，從a對應的頂點i到b對應的頂點j連接一條容量為1，費用為區間長度的有向邊。

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

【建模分析】

這個問題可以看做是求K條權之和最大的不相交路徑，每條路徑為一些不相交的區間序列。由于是最大費用流，兩條路徑之間一定有一些區間相交，可以看作是相交部分重復了2次，而K條路經就是最多重復了K次。最簡單的想法就是把區間排序后，不相交的區間之間連接一條邊，由于每個區間只能用一次，所以要拆點，點內限制流量。如果我們改變一下思路，把端點作為網絡中的頂點，區間恰恰是特定一些端點之間的邊，這樣建模的復雜度更小。方法1的邊數是O(N^2)的，而方法2的邊數是O(N)的，可以解決更大規模的問題。

#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 1000 + 10, M = 100000 + 10, inf = 0x3f3f3f3f;struct Edge{ int fr, to, cap, flow, cost;}edg[M];int nxt[M], hd[N], tot;int n, k;int s, t;int q[N], inq[N], p[N], a[N], d[N];int l[N], r[N], w[N], hs[N], cnt;void insert(int u, int v, int w, int x){ edg[tot].fr = u, edg[tot].to = v, edg[tot].cap = w, edg[tot].flow = 0, edg[tot].cost = x; nxt[tot] = hd[u]; hd[u] = tot; tot++; edg[tot].fr = v, edg[tot].to = u, edg[tot].cap = 0, edg[tot].flow = 0, edg[tot].cost = -x; nxt[tot] = hd[v]; hd[v] = tot; tot++;}bool spfa(int &fl, int &cst){ for(int i = s; i <= t; i++) d[i] = -inf; d[s] = 0; p[s] = 0; a[s] = inf; int head = 0, tail = 1; q[0] = s; inq[s] = 1; while(head != tail){ int u = q[head++]; if(head == 1001) head = 0; inq[u] = 0; for(int i = hd[u]; i >= 0; i = nxt[i]){ Edge &e = edg[i]; if(d[e.to] < d[u] + e.cost && e.cap > e.flow){ d[e.to] = d[u] + e.cost; p[e.to] = i; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]){ q[tail++] = e.to; if(tail == 1001) tail = 0; inq[e.to] = 1; } } } } if(d[t] == -inf) return false; fl += a[t]; cst += a[t] * d[t]; int u = t; while(u != s){ edg[p[u]].flow += a[t]; edg[p[u]^1].flow -= a[t]; u = edg[p[u]].fr; } return true;}void init(){ scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++){ scanf("%d%d", &l[i], &r[i]); w[i] = r[i] - l[i]; hs[++cnt] = l[i]; hs[++cnt] = r[i]; } sort(hs + 1, hs + cnt + 1); for(int i = 1; i <= n; i++){ l[i] = lower_bound(hs + 1, hs + cnt + 1, l[i]) - hs; r[i] = lower_bound(hs + 1, hs + cnt + 1, r[i]) - hs; }}void build(){ s = 0, t = n * 2 + 1; memset(hd, -1, sizeof(hd)); insert(s, 1, k, 0); insert(n * 2, t, k, 0); for(int i = 1; i < n * 2; i++) insert(i, i + 1, inf, 0); for(int i = 1; i <= n; i++) insert(l[i], r[i], 1, w[i]);}void work(){ build(); int flow = 0, cost = 0; while(spfa(flow, cost));