建图（(x,y,c,l)表示x到y，费用c，流量l）

(S,1,0,K)

(i,i+1,0,K) 这个边上的流量，表示i还可以被覆盖的次数

(N,T,0,K)

(i,j,w,1)对于权值为w的区间[i,j]

然后跑最大费用最大流

因为没有负权值，所以肯定尽量跑满

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define CLR(a,x) memset(a,x,sizeof(a)) 6 #define MP make_pair 7 using namespace std; 8 typedef long long ll; 9 typedef unsigned long long ull;10 typedef pair
         
           pa;11 const int maxn=205,maxp=410,inf=1e9;12 13 inline ll rd(){14     ll x=0;char c=getchar();int neg=1;15     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();}16     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();17     return x*neg;18 }19 20 int l[maxn],r[maxn],w[maxn],N,M,K,tmp[maxp],S=405,T=406;21 struct Edge{22     int b,l,ne,c;23 }eg[maxp*3];24 int egh[maxp],ect=1;25 int dis[maxp],fae[maxp];26 bool flag[maxp];27 28 inline void adeg(int a,int b,int c,int l){29     // printf("~%d %d %d %d\n",a,b,c,l);30     eg[++ect].b=b,eg[ect].l=l,eg[ect].c=c,eg[ect].ne=egh[a],egh[a]=ect;31     eg[++ect].b=a,eg[ect].l=0,eg[ect].c=-c,eg[ect].ne=egh[b],egh[b]=ect;32 }33 34 queue
          
            q;35 inline bool spfa(){36 CLR(dis,-1);dis[S]=0;37 CLR(fae,0);q.push(S);38 while(!q.empty()){39 int p=q.front();q.pop();40 // printf("~%d %d\n",p,dis[S]);41 flag[p]=0;42 for(int i=egh[p];i;i=eg[i].ne){43 int b=eg[i].b;if(!eg[i].l) continue;44 // printf("!!%d %d %d\n",b,eg[i].c,eg[i].l);45 if(dis[b]
           
            =0;52 }53 54 int main(){55 //freopen("","r",stdin);56 int i,j,k;57 for(int t=rd();t;t--){58 N=rd(),K=rd();59 for(i=1;i<=N;i++){60 tmp[i]=l[i]=rd(),tmp[i+N]=r[i]=rd(),w[i]=rd();61 }sort(tmp+1,tmp+N+N+1);62 int M=unique(tmp+1,tmp+N+N+1)-tmp-1;63 CLR(egh,0);ect=1;64 for(i=1;i<=N;i++){65 l[i]=lower_bound(tmp+1,tmp+M+1,l[i])-tmp;66 r[i]=lower_bound(tmp+1,tmp+M+1,r[i])-tmp;67 adeg(l[i],r[i],w[i],1);68 }69 for(i=1;i