http://acm.hdu.edu.cn/showproblem.php?pid=2119
一个由0和1构成的矩阵,每次选取一行或者一列将其中的1变成0,求最小删除次数
简单的二分图应用,矩阵的横坐标和纵坐标看成二分图的两个集合,为1 就代表两点有连通,最小删除次数就是求最小覆盖点数,而最小覆盖点数等于最大匹配数
#include<cstdio>
#include<cstring>
using namespace std;
#define M 150
int map[M][M],p[M],used[M],n,m;
int sreach(int x)
{
int i;
for (i=;i<=m;i++)
{
if (map[x][i]&&!used[i])
{
used[i]=;
if (!p[i]||sreach(p[i])){
p[i]=x;
return ;
}
}
}
return ;
}
int main()
{
int i,j;
while(~scanf("%d",&n))
{
if (!n) break;
scanf("%d",&m);
for (i=;i<=n;i++){
for (j=;j<=m;j++)
scanf("%d",&map[i][j]);
}
int ans=;
memset(p,,sizeof(p));
for (i=;i<=n;i++)
{
memset(used,,sizeof(used));
if (sreach(i)) ans++;
}
printf("%d\n",ans);
}
return ;
}