题目大概是，一个数轴上n个线段，每个线段都有起始坐标、长度和权值，问从中取出没有公共交点的线段的最大权和。
取k次是个经典的最小费用最大流问题，不过这题建容量网络有20W个点，离散化最多也要6W个点，跑不动最小费用最大流的样子。。
其实这题也是个经典的DP，区间图最大权独立集问题，《挑战程序设计竞赛》有介绍。
- dp[i]表示坐标在[0,i]范围内能得到的最大的线段权值和
- dp[i]=max(dp[i-1],max(dp[j]+w)（[j,i]是一条权w的线段）)
用左闭右开的区间表示这道题的线段。用邻接表存一下各个坐标是哪几条线段的右端点，这样时间复杂度就是O(n+m)，n为线段数，m为坐标最大值。
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
struct Edge{
int v,w,next;
}edge[];
int NE,head[];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
head[u]=NE++;
}
int d[];
int main(){
int t,n,a,b,c;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
NE=;
memset(head,-,sizeof(head));
scanf("%d",&n);
int mx=;
while(n--){
scanf("%d%d%d",&a,&b,&c);
addEdge(a+b,a,c);
mx=max(mx,a+b);
}
for(int i=; i<=mx; ++i){
d[i]=d[i-];
for(int j=head[i]; j!=-; j=edge[j].next){
d[i]=max(d[i],d[edge[j].v]+edge[j].w);
}
}
printf("Case %d: %d\n",cse,d[mx]);
}
return ;
}