[网络流24题]最长k可重线段集[题解]

时间：2023-12-21 16:42:38

最长 \(k\) 可重线段集

题目大意

给定平面 \(x-O-y\) 上 \(n\) 个开线段组成的集合 \(I\) ，和一个正整数 \(k\) 。试设计一个算法，从开线段集合 \(I\) 中选取开线段集合 \(S \subseteq I\) ，使得在 \(x\) 轴上的任意一点 \(P\) ， \(S\) 中与直线 \(x=p\) 相交的开线段个数不超过 \(k\) ，且 \(\sum_{z \in S}|z|\) 最大。这样的集合 \(S\) 称为开线段集合 \(I\) 的最长 \(k\) 可重线段集。 \(\sum_{z\in S}|z|\) 称为最长 \(k\) 可重线段集的长度。

对于任意开线段 \(z\) ，设其端点坐标为 \((x_0,y_0)\) 和 \((x_1,y_1)\) ，则开线段 \(z\) 的长度 \(|z|\) 定义为：

\[|z|=[\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}]
\]

对于给定的开线段集合 \(I\) 和正整数 \(k\) ，计算开线段集合 \(I\) 的最长 \(k\) 可重线段集的长度。

分析

想要解决此题，可以先看一下与该题基本如出一辙的：最长 \(k\) 可重区间集[题解]

其实这道题和上述此题非常类似，只不过将水平的区间转化为了一些基本无规律处于二维平面内的线段。

那么我们还是可以把问题转化到 \(x\) 上，我们发现其实 \(y\) 坐标和题目的限制关系不大，我们只需要解决横坐标部分即可。

其实我们只需要把线段两个端点的 \(x\) 坐标转化为何上述题目一样的区间即可，就可以得到和上述题目一样的过程，具体分析可以点击上方链接，下面直接给出建图思路：

  • 将每个线段的左右端点的 \(x\) 坐标储存起来，并将线段 \(i\) 拆成 \(i\) 与 \(i'\) 分别表示点 \(i\) 的入点与出点，对于每对拆点，在他们中间连接一条流量为 \(1\) ，费用为线段长度的边。

  • 建立一个超级源点和超级汇点，超级源点向真正的源点连接一条流量为 \(k\) ，费用为 \(0\) 的边，并再将源点向每条线段的入点连接一条流量为 \(1\) ，费用为 \(0\) 的边，每条线段的出点向超级汇点连接一条流量为 \(1\) ，费用为 \(0\) 的边。

  • 对于左右端点形成的区间互不相交的线段，在他们之间建立一条流量为 \(+\infty\) ，费用为 \(0\) 的边。

这样就可以直接跑最大费用了。

需要注意两个地方：

  • 本文一开始的链接中详细论述了线段连接有序性的必要，所以我们必须要排序或是要保证线段连接的有序。

  • 对于两条线段，如果他们完全相同的话，我们仍然需要将其计算在限制内，所以需要进行特殊判断，不能进行连边。

最后代码如下：

CODE

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N=5e2+10,INF=0x7fffffff;

int n,k,s,t,_s,ans;

struct node{ int l,r,len; }sec[N];

inline int read()

{

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();

	return s*w;

}

inline bool cmp(node x,node y) { return x.l<y.l; }

int tot=-1,v[2*N*N],w[2*N*N],pay[2*N*N],nex[2*N*N],first[2*N];

inline void Add(int x,int y,int z,int c)

{

	nex[++tot]=first[x];

	first[x]=tot;

	v[tot]=y,w[tot]=z,pay[tot]=c;

}

bool vis[2*N];

int pre[2*N],dis[2*N],Min[2*N];

inline bool SPFA()

{

	for(register int i=s;i<=t;i++) dis[i]=-INF;

	for(register int i=s;i<=t;i++) vis[i]=false;

	queue<int> q;

	q.push(s);

	vis[s]=true,dis[s]=0,Min[s]=INF;

	while(!q.empty()){

		int now=q.front(); q.pop();

		vis[now]=false;

		for(register int i=first[now];i!=-1;i=nex[i]){

			int to=v[i];

			if(!w[i]) continue;

			if(dis[to]<dis[now]+pay[i]){

				dis[to]=dis[now]+pay[i];

				Min[to]=min(Min[now],w[i]);

				pre[to]=i;

				if(!vis[to]) q.push(to),vis[to]=true;

			}

		}

	}

	return dis[t]!=-INF;

}

inline void EK()

{

	while(SPFA()){

		ans+=Min[t]*dis[t];

		int temp=t,i;

		while(temp!=s){

			i=pre[temp];

			w[i]-=Min[t];

			w[i^1]+=Min[t];

			temp=v[i^1];

		}

	}

}

signed main()

{

	memset(first,-1,sizeof(first));

	n=read(),k=read();

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

		int _x1=read(),_y1=read(),_x2=read(),_y2=read();

		sec[i].l=min(_x1,_x2),sec[i].r=max(_x1,_x2);

		sec[i].len=(int)sqrt((_x1-_x2)*(_x1-_x2)+(_y1-_y2)*(_y1-_y2));

	}

	s=0,_s=2*n+1,t=2*n+2;

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

	Add(s,_s,k,0),Add(_s,s,0,0);

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

		Add(_s,i,1,0),Add(i,_s,0,0);

		Add(i,i+n,1,sec[i].len),Add(i+n,i,0,-sec[i].len);

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

	}

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

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

            if(sec[i].l==sec[i].r&&sec[j].l==sec[j].r&&sec[i].l==sec[j].l) continue;

    		if(sec[j].l>=sec[i].r||sec[i].l>=sec[j].r) Add(i+n,j,INF,0),Add(j,i+n,0,0);

		}

	}

	EK();

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

	return 0;

}

相关文章