最长可重区间集 spfa费用流

给定实直线L上的n个开区间，和一个正整数k

选取若干个区间，在保证实直线L上的任意一个点最多被选出区间覆盖k次的情况下，使得这些区间的长度和最大

先把区间按照左端点排序，

考虑到重复其实就代表着相交，

可以把问题转化为选出k组组内不相交区间，使得他们区间长度和最大。

从源点S向每个区间左端点连一条容量1费用0的边，每个区间右端点向汇点T连一条容量1费用0的边。用来限制每条边只能选一次。

每个区间左端点向右端点连一条容量1费用为区间长度的边

每个区间右端点向所有数值比它大的其他区间左端点连一条容量1费用0的边。

求最大费用最大流即可。（将所有费用取相反数然后求最小费用最大流）

代码如下

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int MAXN=10100;
const int maxn=1010;
const int INF=~0U>>1;
int maxflow=0,cost=0;
int pre[maxn],vis[maxn],dis[maxn];
int S,Sa,T;
int n,k;
int tot=0;
int pointer[maxn];
struct qj{
    int l;int r;
}a[maxn];
struct Edge
{
    int to,next,cap,op,f,w;
    Edge() {};
    Edge(int b,int c,int nxt,int num,int flow,int weight) {to=b,cap=c,next=nxt,op=num^1,f=flow,w=weight;}
}edge[MAXN];
inline void addedge(int a,int b,int c,int w1)
{
    edge[tot]=Edge(b,c,pointer[a],tot,0,w1);
    pointer[a]=tot++;
    edge[tot]=Edge(a,0,pointer[b],tot,0,-w1);
    pointer[b]=tot++;
}
bool cmp(qj A,qj B)
{
    return A.l<B.l;
}
void init()
{
    memset(pointer,-1,sizeof(pointer));
    scanf("%d%d",&n,&k);
    int l,r;
    rep(i,1,n)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
      //  printf("i=%d l=%d r=%d
",i,a[i].l,a[i].r);
    }
    sort(a+1,a+n+1,cmp);
    S=0;
    Sa=2*n+1;T=2*n+2;
    addedge(S,Sa,k,0);
    rep(i,1,n)
    {
        addedge(Sa,i,1,0);
        addedge(i,n+i,1,a[i].l-a[i].r);
        rep(j,i+1,n)
        {
            if(a[j].l>=a[i].r)
            {
                addedge(n+i,j,1,0);
            }
        }
        addedge(n+i,T,1,0);
    }
}
bool spfa(int s,int t)
{
    queue<int > q;
    rep(i,S,T)
    {
        dis[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    dis[S]=0;
    vis[S]=1;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int j=pointer[u];j!=-1;j=edge[j].next)
        {
            int v=edge[j].to;
            if(edge[j].cap-edge[j].f>0&&dis[v]>dis[u]+edge[j].w)
            {
                dis[v]=dis[u]+edge[j].w;
                pre[v]=j;
                if(!vis[v])
                {
                    vis[v]=1;q.push(v);
                }
            }
        }
    }
    if(pre[T]==-1) return false;
    else return true;
}
int mcmf()
{
    int flow=0;
    cost=0;
    while(spfa(S,T))
    {
        int mi=INF;
        for(int i=pre[T];i!=-1;i=pre[edge[i^1].to])
        {
            mi=min(mi,edge[i].cap-edge[i].f);
        }
        for(int i=pre[T];i!=-1;i=pre[edge[i^1].to])
        {
            edge[i].f+=mi;
            edge[i^1].f-=mi;
            cost+=edge[i].w*mi;
        }
        flow+=mi;
    }
    return flow;
}
int main()
{
    freopen("interv0.in","r",stdin);
  //  freopen("why.txt","w",stdout);
    init();
    mcmf();
    printf("%d",-cost);
    return 0;
}