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āi)區(qū)間，每個(gè)區(qū)間配一個(gè)權(quán)值。
問(wèn)：在區(qū)間每個(gè)點(diǎn)不被重疊k次能取到的最大權(quán)值。
分析：區(qū)間內(nèi)每個(gè)點(diǎn)不能被重疊k次。則每個(gè)點(diǎn)可以配一個(gè)容量為k的邊。設(shè)k為1，這樣一段區(qū)間A包含區(qū)間B，則B的權(quán)限比A的低，因?yàn)锽要選取得看看A是否被選取，如果A被選取，則A的左端點(diǎn)已經(jīng)滿(mǎn)了，所以B在權(quán)值小于A的話(huà)是不被選的。對(duì)其他重疊情況也是如此，這樣保證了每個(gè)區(qū)間之多被重疊k次。感覺(jué)這樣構(gòu)圖之后就成了邊連通度的模型了。由于很多點(diǎn)可以被離散化，所以建成圖的點(diǎn)數(shù)就少了。最多也就401個(gè)點(diǎn)。這個(gè)經(jīng)典的構(gòu)圖太帥了，可惜不是自己想的。
代碼：
#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;
}