程序员人生 网站导航

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 抖音有效粉丝500个怎么买(个人分享) 5跨越速运再夺中国零担三甲!连续四年霸榜的密码曝光 6中电核心海外共享充电宝领航者,全球共享充电宝贴牌定制 7e签宝智能合同Agent于数字中国重磅发布!