把行跟列看成二分图的两部分,每个1连接一个行一个列,就是二分图的边,每个边只要选一个点就能删除,所以就是最小顶点覆盖问题,选择最少的点覆盖所有的边
#include<stdio.h> #include<string.h> #define N 110 int map[N][N],match[N],vis[N],n,m; int find(int x) { int i; for(i=1;i<=m;i++) { if(vis[i]==0&&map[x][i]==1) { vis[i]=1; if(match[i]==-1||find(match[i])==1) { match[i]=x; return 1; } } } return 0; } int main() { int i,sum,j,a; while(scanf("%d",&n),n) { memset(map,0,sizeof(map)); memset(match,-1,sizeof(match)); scanf("%d",&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&a); if(a==1) map[i][j]=1; } } sum=0; for(i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); sum+=find(i); } printf("%d\n",sum); } return 0; }