POJ3680 Intervals (区间K覆盖问题)

Intervals

Time Limit: 5000MSMemory Limit: 65536KTotal Submissions: 7606Accepted: 3195

Description

You are given N weighted open intervals. The ith interval covers (a_i, b_i) and weighs w_i. 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 a_i, b_i, w_i(1 ≤ a_i < b_i ≤ 100,000, 1 ≤ w_i ≤ 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 这玩意不和poj3762一模一样吗？？？ 所以直接 传送门 #include<iostream> using namespace std; #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #pragma comment(linker,"/STACK:102400000,102400000") #include<time.h> const int maxn=205*205+200; const int maxm=maxn*8+200; const int inf=0x3f3f3f3f; struct note { int to,next,cost,flow,cap; } edge[maxm]; struct notes{ int l,r,width; }M[205]; int H[maxn]; int head[maxn]; bool used[maxn]; int que[maxm*2]; int d[maxn]; int pre[maxn],n,k,top; inline void ADD(int u,int v,int f,int c) { edge[top].to=v; edge[top].next=head[u]; edge[top].flow=0; edge[top].cap=f; edge[top].cost=c; head[u]=top++; edge[top].to=u; edge[top].next=head[v]; edge[top].flow=0; edge[top].cap=0; edge[top].cost=-c; head[v]=top++; } bool spfa(int s,int t) { int l=0,r=0; memset(used,false,sizeof(used)),memset(d,inf,sizeof(d)),memset(pre,-1,sizeof(pre)); used[s]=true,d[s]=0; que[r++]=s; while(l<r) { int now=que[l++]; used[now]=false; for(int i=head[now]; ~i; i=edge[i].next) { int to=edge[i].to; if((edge[i].cap>edge[i].flow)&&(edge[i].cost+d[now]<d[to])) { d[to]=d[now]+edge[i].cost; pre[to]=i; if(!used[to]) { used[to]=true,que[r++]=to; } } } } return pre[t]!=-1; } int mcmf(int s,int t,int &cost) { cost=0; int maxflow=0,Min; while(spfa(s,t)) { Min=inf; for(int i=pre[t]; ~i; i=pre[edge[i^1].to]) { if(Min>(edge[i].cap-edge[i].flow)) { Min=edge[i].cap-edge[i].flow; } } maxflow+=Min; for(int i=pre[t]; ~i; i=pre[edge[i^1].to]) { cost+=(edge[i].cost*Min); edge[i].flow+=Min; edge[i^1].flow-=Min; } } return maxflow; } int main() { #ifdef tangge freopen("3680.txt","r",stdin); #endif // tangge int pos1,pos2,Tcase; scanf("%d",&Tcase); while(Tcase--) { scanf("%d%d",&n,&k); int len=0; for(int i=0;i<n;++i){ scanf("%d%d%d",&M[i].l,&M[i].r,&M[i].width); H[len++]=M[i].l,H[len++]=M[i].r; } sort(H,H+len); int newlen=unique(H,H+len)-H; top=0; memset(head,-1,sizeof(head)); int S=0,T=newlen; for(int i=1;i<newlen-1;++i){ ADD(i,i+1,k,0); } for(int i=0;i<n;++i){ pos1=lower_bound(H,H+newlen,M[i].l)-H+1; pos2=lower_bound(H,H+newlen,M[i].r)-H+1; ADD(pos1,pos2,1,-M[i].width); } ADD(S,1,k,0); ADD(newlen-1,T,k,0); int cost; mcmf(S,T,cost); printf("%d\n",-cost); } return 0; }