经典题，融合了最大流与费用流的精华

算法当然选用最大费用流

离散化并排序所有点，对于每个区间(x,y)，连x->y的边，费用W，流量1。对于所有(x,x+1)，连费用0，流量k的边。

原理是：对于两条部分重合的线段，它们总是使用不同的两股流。

代码：
#include <cstdio>
#include <string.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
const int NMax=450;
struct edge {
    int num,len,C;
    edge *next,*rev;
}*A[NMax],pool[NMax*4];
int N,nn,M,L;
void Build(int x,int y,int z,int c) {
    edge *p=&pool[L++],*q=&pool[L++];
    p->num=y;p->len=z;p->C=c;p->next=A[x];A[x]=p;p->rev=q;
    q->num=x;q->len=0;q->C=-c;q->next=A[y];A[y]=q;q->rev=p;
} 
int X[NMax],Y[NMax],Z[NMax],pre[NMax],dist[NMax];
edge *pre1[NMax];
bool inq[NMax];
map<int,int> MAP;
int M1[NMax],L2;
queue<int> Q;
int Dinic() {
    int ret=0;
    while(1) {
        memset(dist,-1,sizeof(dist));
        memset(pre,-1,sizeof(pre));
        memset(pre1,0,sizeof(pre1));
        memset(inq,0,sizeof(inq));
        dist[0]=0;Q.push(0);inq[0]=1;
        while(!Q.empty()) {
            int x=Q.front();Q.pop();inq[x]=0;
            for(edge *p=A[x];p;p=p->next) if(p->len&&dist[x]+p->C>dist[p->num]) {
                dist[p->num]=dist[x]+p->C;
                pre[p->num]=x;pre1[p->num]=p;
                if(!inq[p->num]) {
                    inq[p->num]=1;
                    Q.push(p->num);
                }
            }
        }
        if(dist[nn]==-1) break;
        int p=nn,Minn=100000000;
        while(pre[p]!=-1) {
            if(pre1[p]->len<Minn) Minn=pre1[p]->len;
            p=pre[p];
        }
        p=nn;
        while(pre[p]!=-1) {
            ret+=pre1[p]->C*Minn;
            pre1[p]->len-=Minn;
            pre1[p]->rev->len+=Minn;
            p=pre[p];
        }
    }
    return ret;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) {
        L2=0;L=0;MAP.clear();
        memset(A,0,sizeof(A));
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++) {
            scanf("%d%d%d",X+i,Y+i,Z+i);
            if(!MAP[X[i]]) {
                MAP[X[i]]=1;
                M1[++L2]=X[i];
            }
            if(!MAP[Y[i]]) {
                MAP[Y[i]]=1;
                M1[++L2]=Y[i];
            }
        }
        MAP.clear();
        sort(M1+1,M1+L2+1);
        for(int i=1;i<=L2;i++) MAP[M1[i]]=i;
        nn=L2+1;
        for(int i=1;i<=nn;i++) Build(i-1,i,M,0);
        for(int i=1;i<=N;i++) Build(MAP[X[i]],MAP[Y[i]],1,Z[i]);
        printf("%d\n",Dinic());
    }    
    getchar();getchar();
    return 0;
}