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 ≤ KN ≤ 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

`43 11 2 22 3 43 4 83 11 3 22 3 43 4 83 11 100000 1000001 2 3100 200 3003 21 100000 1000001 150 301100 200 300`

Sample Output

`1412100000100301`

#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;
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
e[cnt].u
= v, e[cnt].v = u, e[cnt].c = 0, e[cnt].f = 0;
e[cnt].w
}
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++)
{
+ 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;