给定实直线 L 上 n 个开区间组成的集合 I，和一个正整数 k，试设计一个算法，从开区间集合 I 中选取出开区间集合 S⊆I，使得在实直线 L 的任何一点 x，S 中包含点 x 的开区间个数不超过 k，且
第 1 行有 2 个正整数 n 和 k，分别表示开区间的个数和开区间的可重迭数。接下来的 n 行，每行有 2 个整数，表示开区间的左右端点坐标。
输出计算出的最长 k 可重区间集的长度。
4 2 1 7 6 8 7 10 9 13
15
搬运的题解，不得不说方法二太巧妙了。。
【问题分析】
最大权不相交路径问题，可以用最大费用最大流解决。
【建模方法】
方法1
按左端点排序所有区间，把每个区间拆分看做两个顶点
1、连接S到S’一条容量为K，费用为0的有向边。 2、从S’到每个
求最大费用最大流，最大费用流值就是最长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)); PRintf("%d/n", cost);}int main(){ freopen("prog821.in", "r", stdin); freopen("prog821.out", "w", stdout); init(); work(); return 0;}新闻热点
疑难解答
