程序员人生 网站导航

POJ 3680 Intervals

栏目:互联网时间:2014-10-09 00:38:43

离散化+最大费用最大流...


源点---1 .. 2 ..3 .... n ---汇点 连流量为K,费用为0的边

对于(a , b , w) 连从 a到b容量1费用w的边


Intervals
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 6503   Accepted: 2691

Description

You are given N weighted open intervals. The ith interval covers (aibi) 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 aibiwi(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

Source

POJ Founder Monthly Contest
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐

1.cyou 非常适合 Z 世代企业家的三大理由 2阿里、京东类ChatGPT产品正在内测 未来或将融入产品 3公会积极复工复产,2023直播行业有哪些新机遇? 4 b站能买粉丝吗,会不会被发现(个人解说) 5 今日头条号买粉会被发现吗(个人爆料) 6 小红书1000粉丝可以买到吗(个人爆料) 7 小红书100粉丝在哪里买,多少钱(姐妹推荐)