1.http://acm.hdu.edu.cn/showproblem.php?pid=2063
分析：直观的二分图题，二分图到底是无向的还是有向的？？在这里若设为无向的则WA，改为有向的则AC，不过网上资料都说二分图是无向图。。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define N 505 5 int k, n, m; 6 bool partner[N][N], used[N]; 7 int match[N]; 8 9 bool find(int x) 10 { 11 for (int i=1; i<=n; i++) 12 { 13 if (!used[i] && partner[x][i]) 14 { 15 used[i] = true; 16 if (match[i]==-1 || find(match[i])) 17 { 18 match[i] = x; 19 return true; 20 } 21 } 22 } 23 return false; 24 } 25 26 void Hungary () 27 { 28 int cnt=0; 29 memset (match, -1, sizeof match); 30 for (int i=1; i<=m; i++) 31 { 32 memset (used, 0, sizeof used); 33 if (find(i)) 34 cnt++; 35 } 36 printf ("%d\n",cnt); 37 } 38 int main () 39 { 40 while (~scanf ("%d",&k) && k) 41 { 42 int a, b; 43 scanf ("%d%d",&m, &n); 44 memset (partner, 0, sizeof partner); 45 while (k--) 46 { 47 scanf("%d%d",&a, &b); 48 partner[a][b] = 1; 49 } 50 Hungary(); 51 } 52 return 0; 53 }
2.http://acm.hdu.edu.cn/showproblem.php?pid=2119
题意：在一个N*M的矩阵中仅有0,1组成，假设每次都可以消去一行或者一列的全部 1，问你最少要几次把全部的 1 消去？
分析：如果我们以 X 和 Y 坐标来分别表示二分图的 X 部分 Y 部分，把1的X，Y位置连一条线。那么一个点覆盖的意义就是，一次能够消灭的所有1的位置，那么最少点覆盖就是我们要求就的答案了。根据二分图的性质：最小点覆盖 = 最大匹配。所以就转化为了求最大匹配问题。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define N 105 5 int n, m; 6 bool used[N]; 7 int match[N], map[N][N]; 8 9 bool find(int x) 10 { 11 for (int i=1; i<=m; i++) 12 { 13 if (!used[i] && map[x][i]) 14 { 15 used[i] = true; 16 if (match[i]==-1 || find(match[i])) 17 { 18 match[i] = x; 19 return true; 20 } 21 } 22 } 23 return false; 24 } 25 26 void Hungary () 27 { 28 int cnt=0; 29 memset (match, -1, sizeof match); 30 for (int i=1; i<=n; i++) 31 { 32 memset (used, 0, sizeof used); 33 if (find(i)) 34 cnt++; 35 } 36 printf ("%d\n",cnt); 37 } 38 int main () 39 { 40 while (~scanf ("%d",&n) && n) 41 { 42 scanf ("%d",&m); 43 memset (map, 0, sizeof map); 44 for (int i=1; i<=n; i++) 45 for (int j=1; j<=m; j++) 46 scanf ("%d",&map[i][j]); 47 Hungary (); 48 } 49 return 0; 50 }
原文：http://www.cnblogs.com/khan724/p/4078596.html
