首页 > 代码库 > 二分图入门题
二分图入门题
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 }
二分图入门题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。