程序员人生 网站导航

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三维天地亮相全球工业互联网大会 分享AI赋能数据治理前沿实践 5公众号买500个粉丝对账号有影响吗(实话分享) 6AI驱动标准化新时代:三维天地亮相东盟论坛,分享检验检测行业智慧变革 7 bilibili粉丝1000可以买吗(个人揭秘)