【AtCoder Regular Contest 092】C.2D Plane 2N Points【匈牙利算法】

题意：给定N个红点二维坐标N个蓝点二维坐标，如果红点横纵坐标都比蓝点小，那么它们能够构成一组。问最多能构成多少组。

题解：把满足要求的红蓝点连线，然后就是匈牙利算法（详情见这里，写的好棒！）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=160;
 7 int a[maxn],b[maxn],c[maxn],d[maxn];
 8 bool used[maxn];
 9 int girl[maxn],line[maxn][maxn];
10 int n;
11 
12 bool Find(int x)
13 {
14     for(int j=1;j<=n;j++)
15     {
16         if(line[x][j]&&!used[j]){
17             used[j]=1;
18             if(girl[j]==0||Find(girl[j])){
19                 girl[j]=x;
20                 return true;
21             }
22         }
23     }
24     return false;
25 }
26 
27 int main()
28 {
29     cin>>n;
30     for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
31     for(int i=1;i<=n;i++) cin>>c[i]>>d[i];
32     memset(line,0,sizeof(line));
33     for(int i=1;i<=n;i++)
34     {
35         for(int j=1;j<=n;j++){
36             if((a[i]<c[j])&&(b[i]<d[j])){
37                 line[i][j]=1;
38             }
39         }
40     }
41     memset(girl,0,sizeof(girl));
42     int ans=0;
43     for(int i=1;i<=n;i++){
44         memset(used,0,sizeof(used));
45         if(Find(i)) ans++;
46     }
47     cout<<ans<<endl;
48     return 0;
49 }