【网络流24题21】最长k可重区间集问题

时间：2021-09-01 12:52:06

题面戳我

题目描述

对于给定的开区间集合I和正整数k，计算开区间集合I的最长k可重区间集的长度。

输入格式：

的第 1 行有 2 个正整数n和k，分别表示开区间的个数和开区间的可重迭数。接下来的 n行，每行有 2 个整数，表示开区间的左右端点坐标。

输出格式：

将计算出的最长 k可重区间集的长度输出

输入输出样例

输入样例#1：

4 2

1 7

6 8

7 10

9 13

输出样例#1：

15

说明

对于100%的数据，1≤n≤500,1≤k≤3

sol

费用流建图

先把点离散化掉

对于剩下的至多1000各点，每个点向下一个点连容量为k，费用为0的边。

对于每组\(l_i,r_i\)，从\(l_i\)向\(r_i\)连容量为1，费用为长度（即\(r_i-l_i\)）的边。

为了限流量所以源点\(S\)向离散化后第一个点连容量为k费用为0的边，最后一个点向汇点\(T\)连容量为k费用为0的边。（其实只要限一边就可以了）

然后上图中跑最大费用流，可以把费用全部取负然后跑最小费用流。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define inf 1000000000

const int _ = 100005;

struct edge{int to,next,w,cost;}a[_<<1];

int n,k,l[_],r[_],o[_],tot,s,t,head[_],cnt=1,vis[_],pe[_],pv[_];

long long dis[_],ans;

queue<int>Q;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

void link(int u,int v,int w,int cost)

{

	a[++cnt]=(edge){v,head[u],w,cost};

	head[u]=cnt;

	a[++cnt]=(edge){u,head[v],0,-cost};

	head[v]=cnt;

}

bool spfa()

{

	memset(dis,63,sizeof(dis));

	dis[s]=0;Q.push(s);

	while (!Q.empty())

	{

		int u=Q.front();Q.pop();

		for (int e=head[u];e;e=a[e].next)

		{

			int v=a[e].to;

			if (a[e].w&&dis[v]>dis[u]+a[e].cost)

			{

				dis[v]=dis[u]+a[e].cost;

				pe[v]=e;pv[v]=u;

				if (!vis[v]) vis[v]=1,Q.push(v);

			}

		}

		vis[u]=0;

	}

	return dis[t]<dis[0];

}

int main()

{

	n=gi();k=gi();

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

		o[i]=l[i]=gi(),o[i+n]=r[i]=gi();

	sort(o+1,o+2*n+1);

	tot=unique(o+1,o+2*n+1)-o-1;

	for (int i=1,L,R;i<=n;i++)

	{

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

		L=lower_bound(o+1,o+tot+1,l[i])-o;

		R=lower_bound(o+1,o+tot+1,r[i])-o;

		link(L,R,1,l[i]-r[i]);

	}

	for (int i=1;i<tot;i++)

		link(i,i+1,inf,0);

	s=tot+1;t=tot+2;

	link(s,1,k,0);link(tot,t,k,0);

	while (spfa())

	{

		int sum=inf;

		for (int i=t;i!=s;i=pv[i])

			sum=min(sum,a[pe[i]].w);

		for (int i=t;i!=s;i=pv[i])

			a[pe[i]].w-=sum,a[pe[i]^1].w+=sum,ans+=1ll*sum*a[pe[i]].cost;

	}

	printf("%lld\n",-ans);

	return 0;

}

相关文章