最长 k 可重区间集问题题解：

突然想起这个锅还没补，于是来把这里补一下qwq。

1.题意简述：

有\(n\)个开区间，这\(n\)个开区间组成了一个直线\(L\)，要求选择一些区间，使得在直线\(L\)上的任意一点，对于你选择的区间来说，包含这个点的区间个数不超过$k $，且满足区间长度和最大。

2.要点：

• 因为是开区间，所以长度为\(r-l\)

• 所用算法为\(EK\)费用流

3.\(solution1 :\)

首先让我们思考这个过程，我们要选择一些区间，那么限制条件是得给在区间上的。考虑这么一种情况，就是有两个区间互不相交。

这种情况对这两个区间互相之间是不影响的，也就是说这两个区间是可以一起选的。换成网络流考虑，这两个区间是可以连边的。

然后考虑怎么连边，我们发现这道题的连边极其复杂，我们要考虑这些区间的长度，也就是每个区间对应的权值。

如果这个当为点权的话是不好计算的，那么我们就尝试拆点，把区间给拆开，然后把点权当成边权来计算。

照样是将一个点\(x\)拆成入点\(x\)和出点\(x+N\)因为一个区间只能选择\(1\)次，那么，我们给每个点对应的入点和出点之间连接一条流量为1，费用为区间长度的边。这样我们就完成了对与区间点权的转化，把他转化成了边权。

那么我们说到，像上图中那样是可以同时选的，因为这两个点之间不影响，但是具体选不选呢？这得看后面不选这个是否更优。于是，只要满足这两个区间之间没有交，这两个区间之内就可以连边。

然后就是考虑对于每个点只能被\(k\)个点覆盖这个限制，这个限制怎么办？这个限制换一种说法，永远不会选择\(k\)个以上交于一点的区间。每个点被覆盖当且仅当线段的起点或者说是终点被覆盖。

我们把区间抽象成立一条条线段。

然后按着线段的集合进行分层，每一层中的线段是互不相交的

那么最多只能叠上\(k\)层，为什么呢？因为每一层中线段是互不相交的，那么后一层一定与前面的线段有相交。然后找到第\(k\)层的时候，得到的收益一定最大。

那么就对于跑\(k\)次的限制来吧，可以在加一个附加源点进行限流，设定流量为\(k\)，然后用这个点去和每个入点进行连接。这样为什么是对的呢？因为，你发现一件事，你之前连的边之中就是连接的互不相交的边，那么这么来，对于每一个点来说，你就是一层，然后当你跑完后，那么得到的答案即为最大。

（思路有点乱，建议自己理理

那么建模是这样的：

1. 建立一个超级源点\(s\)，在建立一颗附加源点\(S\)，中间连费用为\(0\)，流量为\(k\)的边。
2. 附加源点\(S\)向每一个入点连一条流量为\(1\)，费用为\(0\)的边
3. 每个入点向自己的出点连一条流量为\(1\)，费用为区间长度的边
4. 对于每一个区间，找到一个与它不重的区间，他们之间连一条流量为\(INF\)，费用为\(0\)的边。
5. 建立一个超级汇点\(t\),每一个出点向超级汇点连接一条流量为\(1\)，费用为\(0\)的边。

代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

template<typename T> inline void read(T &x){

    T f=1;x=0;

    char ch=getchar();

    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}

    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

    x*=f;

}

const int N = 4e5,INF=2e9;

int n,k;

struct query{

    int l,r;

}a[N];

bool cmp(query x,query y){

	return x.l<y.l;

}

int nex[N],first[N],v[N],num=1,flow[N],cost[N],pre[N];

void add(int from,int to,int val,int c){

	nex[++num]=first[from];

	first[from]=num;

	v[num]=to;

	flow[num]=val;

	cost[num]=c;

}

int dis[N],vis[N],inf[N],q[N],last[N],mincost;

bool spfa(int s,int t){

	memset(dis,0xcf,sizeof(dis));

	memset(vis,0,sizeof(vis));

	memset(inf,0x7f,sizeof(inf));

	q[1]=s;

	vis[s]=1;

	dis[s]=0;

	pre[t]=-1;

	int l=0,r=1;

	while(l!=r){

		int u=q[++l];

		vis[u]=0;

		for(int i=first[u];i;i=nex[i]){

			int to=v[i];

			if(flow[i] && dis[to]<dis[u]+cost[i]){

				dis[to]=dis[u]+cost[i];

				pre[to]=u;

				last[to]=i;

				inf[to]=min(inf[u],flow[i]);

				if(!vis[to]){

					vis[to]=1;

					q[++r]=to;

				}

			}

		}

	}

	return pre[t]!=-1;

}

void EK(int s,int t){

	while(spfa(s,t)){

		int now=t;

		mincost+=inf[t]*dis[t];

		while(now!=s){

			flow[last[now]]-=inf[t];

			flow[last[now]^1]+=inf[t];

			now=pre[now];

		}

	}

}

int s,t,S;

signed main(){

    read(n),read(k);

    for(int i=1;i<=n;i++){

        read(a[i].l),read(a[i].r);

        if(a[i].l>a[i].r) swap(a[i].l,a[i].r);

    }

    s=0;

    S=4*n;

    t=5*n;

    add(s,S,k,0);

    add(S,s,0,0);

	sort(a+1,a+n+1,cmp);

    for(int i=1;i<=n;i++){

		add(S,i,1,0);

    	add(i,S,0,0);

		add(i,i+n,1,a[i].r-a[i].l);

		add(i+n,i,0,a[i].l-a[i].r);

		add(i+n,t,1,0);

		add(t,i+n,0,0);

	}

    for(int i=1;i<=n;i++){

		for(int j=i+1;j<=n;j++){

    		if(a[j].l>=a[i].r||a[i].l>=a[j].r){

    			add(i+n,j,INF,0);

    			add(j,i+n,0,0);

			}

		}

	}

	EK(s,t);

	cout<<mincost;

    return 0;

}

4.$solution2:\ $

这里有网上的另一种做法，效果更加优异，但是我觉得怪怪的，反正我是没有直接想出来。但是这种做法的复杂度更优，我有空再补把。

这里把几篇讲得看起来很详细得题解拿过来，如果想学习得去看这个把。

1号大佬博客

2号大佬博客

花姐姐的博客

太难为我了，完结了QAQ。