给两种长方形， 水平的和垂直的， 大小都为1*2， n个水平的， m个垂直的， 给出它们的坐标。 水平的和垂直的可以相互覆盖， 但是同种类型的没有覆盖。 去掉一些长方形， 使得剩下的全部都没有覆盖， 求剩下的数量的最大值。
如果一个水平的和一个垂直的相互覆盖， 那么它们之间连一条边， 然后匈牙利匹配求出最大匹配数num， ans = n+m-num;
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; pll a[1005], b[1005]; const int maxn = 1e5+5; int head[maxn*2], num; struct node { int to, nextt; }e[maxn*2]; void add(int u, int v) { e[num].to = v, e[num].nextt = head[u], head[u] = num++; } void init() { num = 0; mem1(head); } int judge(pll x, pll y) { if(x.first == y.first&&x.second==y.second) return 1; if(x.first+1 == y.first&&x.second==y.second) return 1; if(x.fi == y.fi && x.se == y.se+1) return 1; if(x.fi+1 == y.fi&&x.se==y.se+1) return 1; return 0; } int path[maxn], vis[maxn]; int dfs(int u) { for(int i = head[u]; ~i; i = e[i].nextt) { int v = e[i].to; if(!vis[v]) { vis[v] = 1; if(path[v] == -1 || dfs(path[v])) { path[v] = u; return 1; } } } return 0; } int main() { int n, m; while(cin>>n>>m) { if(n+m==0) break; init(); for(int i = 0; i<n; i++) { scanf("%d%d", &a[i].fi, &a[i].se); } for(int i = 0; i<m; i++) { scanf("%d%d", &b[i].fi, &b[i].se); } for(int i = 0; i<n; i++) { for(int j = 0; j<m; j++) { if(judge(a[i], b[j])) { add(i, j+n); } } } int ans = 0; mem1(path); for(int i = 0; i<n; i++) { mem(vis); ans += dfs(i); } cout<<n+m-ans<<endl; } return 0; }