洛谷傳送門

題目描述：

給出N平行于坐標軸的線段，要你選出盡量多的線段使得這些線段兩兩沒有交點（頂點也算），橫的與橫的，豎的與豎的線段之間保證沒有交點，輸出最多能選出多少條線段。

?

因為橫的與橫的，豎的與豎的沒有交點，所以直接把相交的線段相連，然后肯定是個二分圖。

選出多少個線段，就是求二分圖的最大獨立集，等于節(jié)點數(shù)(N) - 最大匹配數(shù)。

由于線段的4個坐標太大?(X1_i, Y1_i) and (X2_i, Y2_i) (1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000)，不能用二維矩陣來記錄。

又看到線段數(shù)量很少?(1 <= N <= 250)，所以可以用結(jié)構(gòu)體來存，然后通過兩重循環(huán)判斷線段是否相連。

——代碼

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 { 12 int pos, minn, maxx; 13 }h[10001], l[10001]; 14 15 void add(int x, int y) 16 { 17 to[cnt] = y; 18 next[cnt] = head[x]; 19 head[x] = cnt++; 20 } 21 22 bool check(int i, int j) 23 { 24 if(h[i].pos < l[j].minn || h[i].pos > l[j].maxx) return 0; 25 if(l[j].pos < h[i].minn || l[j].pos > h[i].maxx) return 0; 26 return 1; 27 } 28 29 bool find(int u) 30 { 31 int i, v; 32 for(i = head[u]; i != -1; i = next[i]) 33 { 34 v = to[i]; 35 if(!vis[v]) 36 { 37 vis[v] = 1; 38 if(!g[v] || find(g[v])) 39 { 40 g[v] = u; 41 return 1; 42 } 43 } 44 } 45 return 0; 46 } 47 48 int main() 49 { 50 int i, j, x1, y1, x2, y2; 51 scanf("%d", &n); 52 memset(head, -1, sizeof(head)); 53 for(i = 1; i <= n; i++) 54 { 55 scanf("%d %d %d %d", &x1, &y1, &x2, &y2); 56 if(x1 == x2) 57 { 58 ++lh; 59 h[lh].pos = x1; 60 h[lh].minn = min(y1, y2); 61 h[lh].maxx = max(y1, y2); 62 } 63 else if(y1 == y2) 64 { 65 ++ll; 66 l[ll].pos = y1; 67 l[ll].minn = min(x1, x2); 68 l[ll].maxx = max(x1, x2); 69 } 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 { 77 memset(vis, 0, sizeof(vis)); 78 if(find(i)) sum++; 79 } 80 printf("%d", n - sum); 81 return 0; 82 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhenghaotian/p/6702200.html

總結(jié)

以上是生活随笔為你收集整理的[USACO11NOV]牛的障碍Cow Steeplechase（匈牙利算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。