P3033 Cow Steeplechase G
FreeTimeLove
·
·
题解
题意
## 思路
我们注意到一共有两种线段：横或竖，而且相同种类线段之间都没有交点。为了使最后所有的线段互不相交，只要两条线段有交点，我们就必须从中删去**至少**一条线段。
那么我们可以进行**二分图最大匹配**，令横和竖分别为左右部点，如果两条线段之间有交点，就令对应的点连边。用匈牙利算法求出最大匹配对数 $cnt$，那么最多可以选 $(n-cnt)$ 条线段。
这样做的正确性是显而易见的。我们用**反证法**证明：
假设删完线段后还有交点，那么在二分图中一定有两个点之间**有边**（因为有交点）而且**都未完成匹配**（否则就被删了），那么此时匈牙利算法还没有结束，与删完线段相矛盾。所以如果删完了线段，一定是没有交点的。
那么为什么我们要求**最多**选几条线段，即**最少**删去几条线段，却用二分图**最大**匹配呢？因为如果两点之间有边，它们所代表的两条线段一定要**至少**删去一条线段。我们用二分图最大匹配求出最大匹配对数 $cnt$，即有 $cnt$ 对线段**不能**同时存在，从中至少删去一条。那么我们从每一对中删去**一**条，既保证了答案没有交点，又让删线段数**最小**，选线段数**最大**，因此最后的答案 $(n-cnt)$ 就是能够选的**最大条数**。
### AC code:
```cpp
#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.