如有错误,请留言提醒,不要坑到小朋友
Description
输入格式:
*第1行:一个整数:N。
*第2 .. N +1行:第i +1包含四个空格分开的整数,代表一个障碍:Y1_i X1_i,X2_i,Y2_i。
SAMPLE INPUT(文件steeple.in):
3
4 5 10 5
6 2 6 12
8 3 8 5
输入详细信息:
有三个可供选择的障碍。第一个是水平段连接(4,5),(10,5),第二和第三是两条垂直线段(6,2),(6,12),(8,3),(8,5) 。
输出格式:
*第1行:FJ可以选择的最大障碍数目。
SAMPLE OUTPUT(文件steeple.out):
2
输出细节:
最佳的方案是选择两个垂直线段(障碍)。
首先,我们很容易看出这是一道二分图的题
题目中说没有横与横,纵与纵不会相交
所以我们只要考虑横纵相交的情况,
我们把相交的横纵连边,就形成了一个二分图
然后n-最大匹配就可以了
#include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #define maxn 50100 using namespace std; struct hg{ int x1,x2,y; hg(){} hg(int x1,int x2,int y):x1(x1),x2(x2),y(y){} }he[maxn]; struct su{ int x,y1,y2; su(){} su(int x,int y1,int y2):x(x),y1(y1),y2(y2){} }sh[maxn]; int sh_tot,he_tot,ans,n,mx[maxn],now[maxn],son[maxn],pre[maxn],tot; bool bb[maxn]; inline void con(int a,int b){ pre[++tot]=now[a]; now[a]=tot; son[tot]=b; } bool check(int i,int j){ if(he[i].x1>sh[j].x||sh[j].x>he[i].x2)return 0; if(sh[j].y1>he[i].y||he[i].y>sh[j].y2)return 0; return 1; } bool bfs(int x){ for(int p=now[x];p;p=pre[p]){ if(bb[son[p]])continue; bb[son[p]]=1; if(!mx[son[p]]||bfs(mx[son[p]])){ mx[son[p]]=x; return 1; } } return 0; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); if(a==c){ if(d<b)swap(d,b); sh[++sh_tot]=su(a,b,d); } else { if(c<a)swap(c,a); he[++he_tot]=hg(a,c,d); } } for(int i=1;i<=he_tot;i++) for(int j=1;j<=sh_tot;j++)if(check(i,j))con(i,j); for(int i=1;i<=he_tot;i++){ memset(bb,0,sizeof(bb)); if(bfs(i))ans++; } printf("%d\n",n-ans); system("pause"); }