自动搬运

查看原文

来自洛谷，原作者为

	FreeTimeLove fAiry tales oF yesterday will grOw but never die

搬运于2025-08-24 21:44:37，当前版本为作者最后更新于2021-11-02 08:03:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

$n$ 条线段或横或竖，横与横、竖与竖之间互不相交，给出每条线段的端点坐标，问从中最多选出几条线段使得被选线段互不相交（一条的端点在另一条线段上也算相交）。

思路

我们注意到一共有两种线段：横或竖，而且相同种类线段之间都没有交点。为了使最后所有的线段互不相交，只要两条线段有交点，我们就必须从中删去至少一条线段。

那么我们可以进行二分图最大匹配，令横和竖分别为左右部点，如果两条线段之间有交点，就令对应的点连边。用匈牙利算法求出最大匹配对数 $cnt$，那么最多可以选 $(n-cnt)$ 条线段。

这样做的正确性是显而易见的。我们用反证法证明：

假设删完线段后还有交点，那么在二分图中一定有两个点之间有边（因为有交点）而且都未完成匹配（否则就被删了），那么此时匈牙利算法还没有结束，与删完线段相矛盾。所以如果删完了线段，一定是没有交点的。

那么为什么我们要求最多选几条线段，即最少删去几条线段，却用二分图最大匹配呢？因为如果两点之间有边，它们所代表的两条线段一定要至少删去一条线段。我们用二分图最大匹配求出最大匹配对数 $cnt$，即有 $cnt$ 对线段不能同时存在，从中至少删去一条。那么我们从每一对中删去一条，既保证了答案没有交点，又让删线段数最小，选线段数最大，因此最后的答案 $(n-cnt)$ 就是能够选的最大条数。

AC code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,n1,tot,nd[N],cnt;
int x1[N],x2[N],y1[N],y2[N],bk[N],a[N],cp[N];
struct edge{
	int v,nxt;
}ed[N];
void add(int u,int v){
	ed[++tot]={v,nd[u]};
	nd[u]=tot;
}
int hung(int u){//匈牙利算法 
	bk[u]=1;
	for(int i=nd[u];i;i=ed[i].nxt){
		int v=ed[i].v;
		if(bk[cp[v]])continue;
		if(cp[v]==0||hung(cp[v]))return cp[v]=u;//相当于return true 
	}
	return 0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
		if(x1[i]>x2[i])swap(x1[i],x2[i]);//不一定x1<=x2,y1<=y2
		if(y1[i]>y2[i])swap(y1[i],y2[i]);
		if(x1[i]==x2[i])a[i]=1,n1++;//竖 
		else a[i]=2;//横 
	}
	for(int i=1;i<n;i++)//有交点就建边 
		for(int j=i+1;j<=n;j++){
			if(a[i]==1&&a[j]==2)
				if(x1[i]>=x1[j]&&x2[i]<=x2[j]&&y1[j]>=y1[i]&&y2[j]<=y2[i])
					add(i,j+n1);
			if(a[i]==2&&a[j]==1)
				if(x1[j]>=x1[i]&&x2[j]<=x2[i]&&y1[i]>=y1[j]&&y2[i]<=y2[j])
					add(j,i+n1);
		}
	for(int i=1;i<=n;i++){
		if(a[i]==2)continue;
		memset(bk,0,sizeof(bk));
		if(hung(i))cnt++;
	}
	cout<<n-cnt<<endl;
	return 0;
}

后记

这其实是二分图求最大独立集类型的典型题目，标准做法即求出最小点覆盖（最大匹配对数），答案即总点数 $-$ 最小点覆盖。

The End.