POJ3680 Intervals —— 区间k覆盖问题（最小费用流）

题目链接：https://vjudge.net/problem/POJ-3680

Intervals

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 8711		Accepted: 3726

Description

You are given N weighted open intervals. The ith interval covers (a_i, b_i) and weighs w_i. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.

Input

The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ K ≤ N ≤ 200).
The next N line each contain three integers a_i, b_i, w_i(1 ≤ a_i < b_i ≤ 100,000, 1 ≤ w_i ≤ 100,000) describing the intervals.
There is a blank line before each test case.

Output

For each test case output the maximum total weights in a separate line.

Sample Input

4

3 1
1 2 2
2 3 4
3 4 8

3 1
1 3 2
2 3 4
3 4 8

3 1
1 100000 100000
1 2 3
100 200 300

3 2
1 100000 100000
1 150 301
100 200 300

Sample Output

Source

POJ Founder Monthly Contest – 2008.07.27, windy7926778

题意：

数轴上有一些带权的区间，选出权值和尽量大的一些区间，使得任意一个数最多被k个区间覆盖。

题解：

可用最小费用流解决，构图方法如下：

1.把数轴上每个数作为一个点。

2.对于相邻的点，连一条边：i-->i+1，容量为k，费用为0。i-->i+1设为k，保证了x-->i（0<=x<i）的流量不高于k。因此，还需在数轴的最右边增加一个汇点，数轴的最后一个点连向此汇点，容量为k，费用为0。

3.对于区间[u, v]，连一条边：u-->v，容量为1，费用为-w。

4.以数轴最左端的点作为源点，跑最小费用流，把得到的最小花费取反，即为答案。

5.由于此题数轴的范围比较大，而实际用到的点却很少，所以可以先对数轴进行离散化。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <cmath>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <string>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 const int INF = 2e9;
 15 const LL LNF = 9e18;
 16 const int mod = 1e9+7;
 17 const int MAXM = 1e5+10;
 18 const int MAXN = 400+10;
 19 
 20 struct Edge
 21 {
 22     int to, next, cap, flow, cost;
 23 }edge[MAXM];
 24 int tot, head[MAXN];
 25 int pre[MAXN], dis[MAXN];
 26 bool vis[MAXN];
 27 int N;
 28 
 29 void init(int n)
 30 {
 31     N = n;
 32     tot = 0;
 33     memset(head, -1, sizeof(head));
 34 }
 35 
 36 void add(int u, int v, int cap, int cost)
 37 {
 38     edge[tot].to = v;  edge[tot].cap = cap;  edge[tot].cost = cost;
 39     edge[tot].flow = 0;   edge[tot].next = head[u];   head[u] = tot++;
 40     edge[tot].to = u;   edge[tot].cap = 0;  edge[tot].cost = -cost;
 41     edge[tot].flow = 0; edge[tot].next = head[v];   head[v] = tot++;
 42 }
 43 
 44 bool spfa(int s, int t)
 45 {
 46     queue<int>q;
 47     for(int i = 0; i<N; i++)
 48     {
 49         dis[i] = INF;
 50         vis[i] = false;
 51         pre[i] = -1;
 52     }
 53 
 54     dis[s] = 0;
 55     vis[s] = true;
 56     q.push(s);
 57     while(!q.empty())
 58     {
 59         int u  = q.front();
 60         q.pop();
 61         vis[u] = false;
 62         for(int i = head[u]; i!=-1; i = edge[i].next)
 63         {
 64             int v = edge[i].to;
 65             if(edge[i].cap>edge[i].flow && dis[v]>dis[u]+edge[i].cost)
 66             {
 67                 dis[v] = dis[u]+edge[i].cost;
 68                 pre[v] = i;
 69                 if(!vis[v])
 70                 {
 71                     vis[v] = true;
 72                     q.push(v);
 73                 }
 74             }
 75         }
 76     }
 77     if(pre[t]==-1) return false;
 78     return true;
 79 }
 80 
 81 int minCostMaxFlow(int s, int t, int &cost)
 82 {
 83     int flow = 0;
 84     cost = 0;
 85     while(spfa(s,t))
 86     {
 87         int Min = INF;
 88         for(int i = pre[t]; i!=-1; i = pre[edge[i^1].to])
 89         {
 90             if(Min>edge[i].cap-edge[i].flow)
 91                 Min = edge[i].cap-edge[i].flow;
 92         }
 93         for(int i = pre[t]; i!=-1; i = pre[edge[i^1].to])
 94         {
 95             edge[i].flow += Min;
 96             edge[i^1].flow -= Min;
 97             cost += edge[i].cost*Min;
 98         }
 99         flow += Min;
100     }
101     return flow;
102 }
103 
104 int interval[220][3];
105 int M[MAXN];
106 int main()
107 {
108     int T, n, k;
109     scanf("%d", &T);
110     while(T--)
111     {
112         scanf("%d%d", &n, &k);
113         int cnt = 0;
114         for(int i = 1; i<=n; i++)
115         {
116             scanf("%d%d%d", &interval[i][0],&interval[i][1],&interval[i][2]);
117             M[cnt++] = interval[i][0];
118             M[cnt++] = interval[i][1];
119         }
120         M[cnt++] = INF;
121         sort(M, M+cnt);
122         cnt = unique(M, M+cnt)-M;
123 
124         init(cnt);
125         for(int i = 0; i<cnt-1; i++)
126         {
127             add(i, i+1, k, 0);
128         }
129         for(int i = 1; i<=n; i++)
130         {
131             int left = lower_bound(M, M+cnt, interval[i][0])-M;
132             int right = lower_bound(M, M+cnt, interval[i][1])-M;
133             add(left, right, 1, -interval[i][2]);
134         }
135 
136         int min_cost;
137         int start = 0, end = cnt-1;
138         minCostMaxFlow(start, end, min_cost);
139         printf("%d\n", -min_cost);
140     }
141 }

View Code

秒客网

POJ3680 Intervals —— 区间k覆盖问题（最小费用流）

相关文章