题解 [USACO11NOV]牛的障碍Cow Steeplechase

Chtholly

题目描述

Farmer John has a brilliant idea for the next great spectator sport: Cow Steeplechase! As everyone knows, regular steeplechase involves a group of horses that race around a course filled with obstacles they must jump over. FJ figures the same contest should work with highly-trained cows, as long as the obstacles are made short enough.

In order to design his course, FJ makes a diagram of all the N (1 <= N <= 250) possible obstacles he could potentially build. Each one is represented by a line segment in the 2D plane that is parallel to the horizontal or vertical axis. Obstacle i has distinct endpoints (X1_i, Y1_i) and (X2_i, Y2_i) (1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000). An example is as follows:

FJ would like to build as many of these obstacles as possible, subject to the constraint that no two of them intersect. Starting with the diagram above, FJ can build 7 obstacles:

Please help FJ determine the maximum number of obstacles he can build.

给出N平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段。

输入输出格式

输入格式

• Line 1: A single integer: N.

• Lines 2..N+1: Line i+1 contains four space-separated integers representing an obstacle: X1_i, Y1_i, X2_i, and Y2_i.
  输出格式

• Line 1: The maximum number of non-crossing segments FJ can choose.

输入输出样例

输入样例#1

3
4 5 10 5
6 2 6 12
8 3 8 5

输出样例#1

2

说明

There are three potential obstacles. The first is a horizontal segment connecting (4, 5) to (10, 5); the second and third are vertical segments connecting (6, 2) to (6, 12) and (8, 3) to (8, 5).

The optimal solution is to choose both vertical segments.

解题思路

根据题意，我们得出如果有两条线段之间有交点，那么这两条线段就只能选择其中一条，所以我们把有交点的线段之间连边，跑一遍匈牙利，找出最大匹配数，然后用n一减就好了
下面是全洛谷跑的最快内存最小最蒟蒻的代码

C++代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define rr register
#define forvec(T,a,it) for(vector<T>::iterator it=a.begin();it!=a.end();++it)
using namespace std;

const int maxn=255;
int n,sum=0;
struct node{
    int pos,far,near;
}heng[maxn],shu[maxn];
int c_heng,c_shu;
int link[maxn],vis[maxn];

inline int read(){
    int chtholly=0,willem=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
    while(c<='9' && c>='0'){chtholly=chtholly*10+(int)(c-'0');c=getchar();}
    return chtholly*willem;
}

inline bool you_jiao_dian(int i,int j){
    if(heng[i].far>=shu[j].pos && heng[i].near<=shu[j].pos && shu[j].far>=heng[i].pos && shu[j].near<=heng[i].pos)
        return 1;
    return 0;
}

inline bool dfs(int x,vector<int>*a){
    forvec(int,a[x],it){
        int v=*it;
        if(!vis[v]){
            vis[v]=1;
            if(link[v]==-1 || dfs(link[v],a)){
                link[v]=x;return 1;
            }
        }
    }
    return 0;
}

inline void max_match(vector<int>*a){
    memset(link,0xff,sizeof(link));
    for(rr int i=1;i<=c_heng;++i){
        memset(vis,0,sizeof(vis));
        if(dfs(i,a))sum++;
    }
}

int main(){
    n=read();
    vector<int>a[n+1];
    for(rr int i=1;i<=n;++i){
        int x1=read(),y1=read(),x2=read(),y2=read();
        if(x1==x2){
            shu[++c_shu].pos=x1;
            shu[c_shu].far=max(y1,y2);
            shu[c_shu].near=min(y1,y2);
        } else if(y1==y2){
            heng[++c_heng].pos=y1;
            heng[c_heng].far=max(x1,x2);
            heng[c_heng].near=min(x1,x2);
        }
    }
    for(rr int i=1;i<=c_heng;++i)
        for(rr int j=1;j<=c_shu;++j)
            if(you_jiao_dian(i,j))
                a[i].push_back(j);
    max_match(a);
    printf("%d\n",n-sum);
    return 0;
}