题目链接：http://poj.org/problem?id=3680
题目大意：有N个带权开区间，让你从中选择一些使得权值最大，实数轴上任意一点被覆盖不超过K次，输出最大权值和。

思路：　经典的在区间上建图题目。首先把所有端点离散化编号从1到n，建立源点0，汇点n+1。对于除汇点之外的点建立从i到i+1的边，容量为K，费用为0。对于每个区间(l,r)，建立从l′到r′的边，容量为1，费用为−wi。跑一遍最小费用最大流，结果的相反数即为答案。

#include  <bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxn=500;
const LL maxm=1e6+10;
struct Mcmf_flow{
    bool vis[maxn];
    LL dis[maxn];
    LL pre[maxn];
    LL last[maxn];
    LL flow[maxn];
    LL zdl, fy;
    LL s1[maxn];//sum的前缀和
    LL sum[maxn];//流量为i的最小费用
    LL tot;
    //dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
    struct Edge {
        LL to,next,flow,dis;//flow流量 dis花费
    } e[maxm<<1];
    LL head[maxn],cut;
    queue <LL> q;
    int N;
    void init(int n){
        N=n+5;
        memset(s1, 0, sizeof(LL)*(N+60));
        memset(sum, 0, sizeof(LL)*(N+60));
        memset(head,-1,sizeof(LL)*(N+60));
        tot=0;
        cut=-1;//初始化
        zdl=fy=0;
    }

    void add_e(LL from,LL to,LL flow,LL dis) {
        e[++cut].next=head[from];
        e[cut].to=to;
        e[cut].flow=flow;
        e[cut].dis=dis;
        head[from]=cut;
    }

    void add(LL x, LL y, LL z, LL f){
        add_e(x,y,z,f);
        add_e(y,x,0,-f);
    }

    bool spfa(LL s,LL t) {
        memset(dis,0x7f,sizeof(LL)*(N+60));
        memset(flow,0x7f,sizeof(LL)*(N+60));
        memset(vis,0,sizeof(bool)*(N+60));
        q.push(s);
        vis[s]=1; dis[s]=0; pre[t]=-1;
        while (!q.empty()) {
            LL now=q.front();
            q.pop(); vis[now]=0;
            for (LL i=head[now]; i!=-1; i=e[i].next) {
                if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].dis) { //正边
                    dis[e[i].to]=dis[now]+e[i].dis;
                    pre[e[i].to]=now;
                    last[e[i].to]=i;
                    flow[e[i].to]=min(flow[now],e[i].flow);//
                    if (!vis[e[i].to]) {
                        vis[e[i].to]=1;
                        q.push(e[i].to);
                    }
                }
            }
        }
        return pre[t]!=-1;
    }

    void MCMF(LL s, LL t) {
        while (spfa(s,t)) {
            LL now=t;
            zdl+=flow[t];
            fy+=flow[t]*dis[t];
            sum[++tot]=fy;//得到sum[]
            s1[tot]=sum[tot]-sum[tot-1];//得到s1[]

            while (now!=s) {
                //从源点一直回溯到汇点
                e[last[now]].flow-=flow[t];//flow和dis容易搞混
                e[last[now]^1].flow+=flow[t];
                now=pre[now];
            }
        }
    }

}min_Flow;


int L[205], R[205], w[205], a[500], tot=0;
int main() {

    int t; scanf("%d", &t);
    while(t--){
        tot=0;
        int n, k; scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++){
            scanf("%d%d%d", &L[i], &R[i], &w[i]);
            a[++tot]=L[i];
            a[++tot]=R[i];
        }
        sort(a+1, a+tot+1);
        int cnt=unique(a+1, a+tot+1)-a-1;
        for(int i=1; i<=n; i++){
            L[i]=lower_bound(a+1, a+cnt+1, L[i])-a;
            R[i]=lower_bound(a+1, a+cnt+1, R[i])-a;
        }
        int S=0, T=cnt+1;
        min_Flow.init(T);
        for(int i=S; i<T; i++){
            min_Flow.add(i, i+1, k, 0);
        }
        for(int i=1; i<=n; i++){
            min_Flow.add(L[i], R[i], 1, -w[i]);
        }
        min_Flow.MCMF(S, T);
        printf("%d\n", -min_Flow.fy);
    }

    return 0;
}