[USACO11NOV]牛的障碍Cow Steeplechase

洛谷传送门

题目描述：

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

因为横的与横的，竖的与竖的没有交点，所以直接把相交的线段相连，然后肯定是个二分图。

选出多少个线段，就是求二分图的最大独立集，等于节点数(N) – 最大匹配数。

由于线段的4个坐标太大 (X1_i, Y1_i) and (X2_i, Y2_i) (1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000)，不能用二维矩阵来记录。

又看到线段数量很少 (1 <= N <= 250)，所以可以用结构体来存，然后通过两重循环判断线段是否相连。

——代码

 #include <cstdio>
 #include <iostream>
 #include <cstring> using namespace std; int n, lh, ll, cnt, sum;
 int next[], to[], head[], g[];
 bool vis[];
 struct node
 {
     int pos, minn, maxx;
 }h[], l[]; void add(int x, int y)
 {
     to[cnt] = y;
     next[cnt] = head[x];
     head[x] = cnt++;
 } bool check(int i, int j)
 {
     if(h[i].pos < l[j].minn || h[i].pos > l[j].maxx) return ;
     if(l[j].pos < h[i].minn || l[j].pos > h[i].maxx) return ;
     return ;
 } bool find(int u)
 {
     int i, v;
     for(i = head[u]; i != -; i = next[i])
     {
         v = to[i];
         if(!vis[v])
         {
             vis[v] = ;
             if(!g[v] || find(g[v]))
             {
                 g[v] = u;
                 return ;
             }
         }
     }
     return ;
 } int main()
 {
     int i, j, x1, y1, x2, y2;
     scanf("%d", &n);
     memset(head, -, sizeof(head));
     for(i = ; i <= n; i++)
     {
         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
         if(x1 == x2)
         {
             ++lh;
             h[lh].pos = x1;
             h[lh].minn = min(y1, y2);
             h[lh].maxx = max(y1, y2);
         }
         else if(y1 == y2)
         {
             ++ll;
             l[ll].pos = y1;
             l[ll].minn = min(x1, x2);
             l[ll].maxx = max(x1, x2);
         }
     }
     for(i = ; i <= lh; i++)
      for(j = ; j <= ll; j++)
       if(check(i, j))
        add(i, j);
     for(i = ; i <= lh; i++)
     {
         memset(vis, , sizeof(vis));
         if(find(i)) sum++;
     }
     printf("%d", n - sum);
     return ;
 }