luogu P3358 最长k可重区间集问题

最大费用最大流，建模方法：

黑线、紫线都是流量k，费用0，保障图的连通性，以及只能走k次

红线代表一个给定的区间，流量1代表只能取一次，费用为区间长度代表走过这条区间，可以获得区间长度的价值

跑最大费用最大流（开始时把边权取反，跑最小费用最大流，然后再取反）

需要离散化😂

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct edge{
    long long v,w,cost,fail;
    edge(){
    }
    edge(long long a,long long b,long long c,long long d){
        v=a;
        w=b;
        cost=c;
        fail=d;
    }
}e[200100];
long long n,k,s,t,m,incf[200100],pre[200100],vis[200100],dis[200100],head[200100],len,last[200100];
long long Left[200100],Right[200010],u[200100],cnt,U[200100],val[200100];
void add(long long x,long long y,long long z,long long c){
    e[len]=edge(y,z,c,head[x]);
    head[x]=len++;
    e[len]=edge(x,0,-c,head[y]);
    head[y]=len++;
}
bool spfa(){
    queue<long long> q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis)); 
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    incf[s]=(long long)1e17;
    while(!q.empty()){
//        cout<<q.front()<<endl;
        long long now=q.front();
        vis[now]=0;
        q.pop();
        for(long long i=head[now];~i;i=e[i].fail){
        //    cout<<i<<endl;
            if(!e[i].w)continue;
            if(dis[e[i].v]>dis[now]+e[i].cost){
                dis[e[i].v]=dis[now]+e[i].cost;
                incf[e[i].v]=min(incf[now],e[i].w);
                pre[e[i].v]=i;
                last[e[i].v]=now;
            //    cout<<"pre of"<<e[i].v<<" is"<<now<<endl;
                if(vis[e[i].v]==0){
                    vis[e[i].v]=1;
                    q.push(e[i].v);
                }
            }
        } 
    }
    //cout<<1<<endl;
    if(dis[t]>=(long long)(1e17))return 0;
    else return 1;
}
long long maxflow=0;
long long ans=0;
long long inf=(long long)1e17;
void update(){
    //cout<<"--------------------------"<<endl;
    long long now=t;
    while(now!=s){
    //    cout<<now<<" "<<last[now]<<endl;
        long long i=pre[now];
        e[i].w-=incf[t];
        e[i^1].w+=incf[t];
        now=last[now];
    } 
    maxflow+=incf[t];
    ans+=dis[t]*incf[t];
    //cout<<ans<<endl;
//    cout<<ans<<endl;
}   
int main(){
    cin>>n>>k;
    memset(head,-1,sizeof(head)); 
    for(int i=1;i<=n;i++){
        cin>>Left[i]>>Right[i];
        u[++cnt]=Left[i];
        u[++cnt]=Right[i];
        val[i]=Right[i]-Left[i];
    }
    sort(u+1,u+cnt+1);
    int cnt1=0;
    for(int i=1;i<=cnt;i++){
        if(u[i]!=u[i-1]){
            U[++cnt1]=u[i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt1;j++){
            if(Left[i]==U[j])Left[i]=j;
            if(Right[i]==U[j])Right[i]=j;
        }
    }
    long long Max=0;
    for(int i=1;i<=n;i++){
        Max=max(Max,Right[i]);
        add(Left[i],Right[i],1,-val[i]);
    }
    n=Max;
    s=0;
    t=Max+1;
    for(int i=1;i<n;i++){
        add(i,i+1,k,0);
    }
    add(s,1,k,0);
    add(n,t,k,0);
    while(spfa())update();
    cout<<-ans<<endl;
}