P3033 [USACO11NOV]牛的障碍Cow Steeplechase
题意
题目描述
--+-------
-----+-----
---+--- |
| | |
--+-----+--+- |
| | | | |
| --+--+--+-+-
| | | |
|
----------
-----------
------- |
| |
| | |
| | | |
| | | |
| | | |
|
给出(N)平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段。
输入输出样例
输入样例#1：
3
4 5 10 5
6 2 6 12
8 3 8 5
输出样例#1：
2
思路
其实这题就一句话：二分图最大独立集大小=总点数-最大匹配数。
二分图匹配就好了。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=255;
int n,ans,match[MAXN],xx[MAXN],yy[MAXN],xxx[MAXN],yyy[MAXN];
int cnt,top[MAXN],to[MAXN*MAXN],nex[MAXN*MAXN];
bool vis[MAXN];
int read()
{
int re=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return re;
}
void add_edge(int x,int y){to[++cnt]=y,nex[cnt]=top[x],top[x]=cnt;}
bool dfs(int now)
{
for(int i=top[now];i;i=nex[i])
if(!vis[to[i]])
{
vis[to[i]]=true;
if(!match[to[i]]||dfs(match[to[i]]))
{
match[to[i]]=now;
return true;
}
}
return false;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
xx[i]=read(),yy[i]=read(),xxx[i]=read(),yyy[i]=read();
if(xx[i]>xxx[i]) swap(xx[i],xxx[i]);
if(yy[i]>yyy[i]) swap(yy[i],yyy[i]);
}
for(int i=1;i<=n;i++)
{
if(xx[i]!=xxx[i]) continue;
for(int j=1;j<=n;j++)
{
if(yy[j]!=yyy[j]) continue;
if(yy[i]<=yy[j]&&yy[j]<=yyy[i]&&xx[j]<=xx[i]&&xx[i]<=xxx[j]) add_edge(i,j);
}
}
for(int i=1;i<=n;i++)
if(xx[i]==xxx[i])
{
memset(vis,false,sizeof vis);
if(dfs(i)) ans++;
}
printf("%d",n-ans);
return 0;
}