http://acm.hdu.edu.cn/showproblem.php?pid=4619
二分图匹配 最小点覆盖 = 最大匹配
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int map[1010][1010]; 7 struct node 8 { 9 int x,y; 10 }p[1010],q[1010]; 11 int n,m,vis[1010],link[1010]; 12 int judge(int i,int j) 13 { 14 if(p[i].x<=q[j].x&&q[j].x<=p[i].x+1) 15 { 16 if(q[j].y<=p[i].y&&p[i].y<=q[j].y+1) 17 return 1; 18 } 19 return 0; 20 } 21 int find(int x) 22 { 23 int i; 24 for(i = 1;i <= m ; i++) 25 { 26 if(map[x][i]&&!vis[i]) 27 { 28 vis[i] = 1; 29 if(link[i]==0||find(link[i])) 30 { 31 link[i] = x; 32 return 1; 33 } 34 } 35 } 36 return 0; 37 } 38 int main() 39 { 40 int i,j,k; 41 while(cin>>n>>m) 42 { 43 if(n==0&&m==0) 44 break; 45 for(i = 1; i <= n ; i++) 46 cin>>p[i].x>>p[i].y; 47 for(i = 1; i <= m ;i++) 48 cin>>q[i].x>>q[i].y; 49 memset(map,0,sizeof(map)); 50 memset(link,0,sizeof(link)); 51 for(i = 1; i <= n ; i++) 52 for(j = 1; j <= m ;j++) 53 if(judge(i,j)) 54 map[i][j] = 1; 55 int sum = 0; 56 for(i = 1; i <= n ; i++) 57 { 58 memset(vis,0,sizeof(vis)); 59 if(find(i)) sum++; 60 } 61 cout<<n+m-sum<<endl; 62 } 63 return 0; 64 }