hdu 2119(简单二分图) Matrix

http://acm.hdu.edu.cn/showproblem.php?pid=2119

一个由0和1构成的矩阵,每次选取一行或者一列将其中的1变成0,求最小删除次数

简单的二分图应用,矩阵的横坐标和纵坐标看成二分图的两个集合,为1 就代表两点有连通,最小删除次数就是求最小覆盖点数,而最小覆盖点数等于最大匹配数

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 #define M 150
 5 int map[M][M],p[M],used[M],n,m;
 6 int sreach(int x)
 7 {
 8     int i;
 9     for (i=1;i<=m;i++)
10     {
11         if (map[x][i]&&!used[i])
12         {
13             used[i]=1;
14             if (!p[i]||sreach(p[i])){
15                 p[i]=x;
16                 return 1;
17             }
18         }
19     }
20     return 0;
21 }
22 int main()
23 {
24     int i,j;
25     while(~scanf("%d",&n))
26     {
27         if (!n) break;
28         scanf("%d",&m);
29         for (i=1;i<=n;i++){
30             for (j=1;j<=m;j++)
31                 scanf("%d",&map[i][j]);
32         }
33         int ans=0;
34         memset(p,0,sizeof(p));
35         for (i=1;i<=n;i++)
36         {
37             memset(used,0,sizeof(used));
38             if (sreach(i)) ans++;
39         }
40         printf("%d
",ans);
41     }
42     return 0;
43 }