[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)，所以可以用结构体来存，然后通过两重循环判断线段是否相连。

——代码

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 5 using namespace std; 6 7 int n, lh, ll, cnt, sum; 8 int next[62501], to[62501], head[251], g[251]; 9 bool vis[251]; 10 struct node 11 h[10001], l[10001]; 14 15 void add(int x, int y) 16 21 22 bool check(int i, int j) 23 28 29 bool find(int u) 30 43 } 44 } 45 return 0; 46 } 47 48 int main() 49 else if(y1 == y2) 64 70 } 71 for(i = 1; i <= lh; i++) 72 for(j = 1; j <= ll; j++) 73 if(check(i, j)) 74 add(i, j); 75 for(i = 1; i <= lh; i++) 76 80 printf("%d", n sum); 81 return 0; 82 }
View Code

上一篇：毕业了！

下一篇：【割点】【割边】tarjan

---

二分图 最大匹配 匈牙利算法