Intervals
Description
You are given N weighted open intervals. The ith interval covers (ai, bi) and weighs wi.
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 ai, bi, wi(1 ≤ ai < bi ≤ 100,000, 1 ≤ wi ≤ 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
14
12
100000
100301
题意：给出一些开区间，每个区间配一个权值。
问：在区间每个点不被重叠k次能取到的最大权值。
分析：区间内每个点不能被重叠k次。则每个点可以配一个容量为k的边。设k为1，这样一段区间A包含区间B，则B的权限比A的低，因为B要选取得看看A是否被选取，如果A被选取，则A的左端点已经满了，所以B在权值小于A的话是不被选的。对其他重叠情况也是如此，这样保证了每个区间之多被重叠k次。感觉这样构图之后就成了边连通度的模型了。由于很多点可以被离散化，所以建成图的点数就少了。最多也就401个点。这个经典的构图太帅了，可惜不是自己想的。
代码：
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#define maxn 1010
#define inf (1 << 28)
using namespace std;
struct Edge
{
int u, v, c, f, w, next;
}e[210000];
int cnt;
int head[maxn], dis[maxn], visit[maxn], pos[maxn];
void addEdge(int u, int v, int c, int w)
{
e[cnt].u = u, e[cnt].v = v, e[cnt].c = c, e[cnt].f = 0;
e[cnt].w = w, e[cnt].next = head[u], head[u] = cnt++;
e[cnt].u = v, e[cnt].v = u, e[cnt].c = 0, e[cnt].f = 0;
e[cnt].w = -w, e[cnt].next = head[v], head[v] = cnt++;
}
void spfa(int s, int t, int ver)
{
int i, j, u, v;
for (i = 0; i <= ver; i++)
{
visit[i] = 0;
dis[i] = -1;
pos[i] = -1;
}
queue <int> que;
que.push(s);
dis[s] = 0;
visit[s] = 1;
while (!que.empty())
{
u = que.front();
que.pop();
visit[u] = 0;
for (i = head[u]; i + 1; i = e[i].next)
{
v = e[i].v;
if (e[i].c > e[i].f && dis[v] < dis[u] + e[i].w)
{
dis[v] = dis[u] + e[i].w;
pos[v] = i;
if (!visit[v])
{
visit[v] = 1;
que.push(v);
}
}
}
}
}
int CostFlow(int s, int t, int ver)
{
int i;
int cost = 0, flow = 0, minf;
while (1)
{
spfa(s, t, ver);
if (dis[t] == -1)
{
break;
}
minf = inf;
for (i = pos[t]; i != -1; i = pos[e[i].u])
{
minf = min(minf, e[i].c - e[i].f);
}
for (i = pos[t]; i != -1; i = pos[e[i].u])
{
e[i].f += minf, e[i^1].f -= minf;
}
flow += minf;
cost += minf * dis[t];
}
return cost;
}
int interval[maxn][3], lsh[maxn];
int cmp(const void * a, const void * b)
{
return *((int*)a) - *((int*)b);
}
int bsc(int l, int r, int x)
{
int mid;
while (l <= r)
{
mid = (l + r ) / 2;
if (lsh[mid] < x)
{
l = mid + 1;
}
else if (lsh[mid] > x)
{
r = mid - 1;
}
else
{
return mid;
}
}
}
int main()
{
int ca, n, k, i, j, m;
scanf("%d", &ca);
while (ca--)
{
scanf("%d%d", &n, &k);
for (i = 0, j = 0; i < n; i++)
{
scanf("%d%d%d", &interval[i][0], &interval[i][1], &interval[i][2]);
lsh[j++] = interval[i][0], lsh[j++] = interval[i][1];
}
qsort(lsh, j, sizeof(int), cmp);
m = j;
for (i = 0, j = 1; j < m; j++)
{
if (lsh[i] != lsh[j])
{
lsh[++i] = lsh[j];
}
}
m = i;
int s = 0, t = m + 1, ver = t + 1;
int u, v;
cnt = 0;
for (i = 0; i <= ver; i++) head[i] = -1;
for (i = 0; i <= m; i++)
{
addEdge(i, i + 1, k, 0);
}
for (i = 0; i < n; i++)
{
u = bsc(0, m, interval[i][0]) + 1;
v = bsc(0, m, interval[i][1]) + 1;
addEdge(u, v, 1, interval[i][2]);
}
int ans = CostFlow(s, t, ver);
printf("%d\n", ans);/**/
}
return 0;
}