题意：
给n给开区间（ai,bi）及相应权值wi，现在要选一些区间，要求任一点不能被超过k个区间覆盖，目标是最大化总的权重。
分析：
转化为求最大费用流，改改最小费用流的模板就好。
代码：
//poj 3680
//sep9
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;
const int maxN=2048;
const int maxM=20024;
const int inf=2000000000;struct Edge
{int v,f,w,nxt;
}e[4*maxM+10];
int g[maxN+10];
int nume,src,sink;
queue<int> Q;
bool inq[maxN+10];
int dist[maxN+10];
int prev[maxN+10],pree[maxN+10];int a[maxN],b[maxN],w[maxN];void addedge(int u,int v,int c,int w)
{e[++nume].v=v;e[nume].f=c;e[nume].w=w;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].w=-w;e[nume].nxt=g[v];g[v]=nume;
}bool find_path()
{while(!Q.empty()) Q.pop();memset(dist,-1,sizeof(dist)); memset(inq,false,sizeof(inq));Q.push(src);inq[src]=true;dist[src]=0;while(!Q.empty()){int u=Q.front();Q.pop();inq[u]=false;for(int i=g[u];i;i=e[i].nxt){if(e[i].f>0&&dist[u]+e[i].w>dist[e[i].v]){dist[e[i].v]=dist[u]+e[i].w;prev[e[i].v]=u;pree[e[i].v]=i; if(!inq[e[i].v]){Q.push(e[i].v);inq[e[i].v]=true;}} } }return dist[sink]==-1?false:true;
}int max_cost_flow(int f)
{int res=0;while(f>0){if(find_path()==false)return -1; int d=f;for(int v=sink;v!=src;v=prev[v])d=min(d,e[pree[v]].f);f-=d;res+=d*dist[sink];for(int v=sink;v!=src;v=prev[v]){e[pree[v]].f-=d;e[pree[v]^1].f+=d;}}return res;
}void init()
{memset(g,0,sizeof(g));nume=1;
}int main()
{int cases;scanf("%d",&cases);while(cases--){init();int i,n,m,k;scanf("%d%d",&n,&k);vector<int> x;for(i=0;i<n;++i){scanf("%d%d%d",&a[i],&b[i],&w[i]);x.push_back(a[i]);x.push_back(b[i]);}sort(x.begin(),x.end());x.erase(unique(x.begin(),x.end()),x.end()); m=x.size();src=m,sink=m+1;addedge(src,0,k,0);addedge(m-1,sink,k,0);for(i=0;i+1<m;++i)addedge(i,i+1,inf,0);for(i=0;i<n;++i){int u=find(x.begin(),x.end(),a[i])-x.begin();int v=find(x.begin(),x.end(),b[i])-x.begin();addedge(u,v,1,w[i]);}printf("%d\n",max_cost_flow(k));} return 0;
}