HDU 2119 Matrix(二分图最小顶点覆盖)

现在我们要选最少的点，让所有的边都消失，那么这个就符合最小顶点覆盖的定义。

继而题目转换为求最小顶点覆盖，而最小顶点覆盖=最大匹配书，继而我们只需要求得最大匹配数即可

相似的题目还有POJ3401，点我传送 (๑ •̀ㅂ•́) ✧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define maxn 1005
using namespace std;

int e[maxn][maxn];
int cy[maxn],vis[maxn];
int n,m,ans;

int path(int u)
{
	for(int v=1;v<=m;v++)
	{
		if(e[u][v]&&!vis[v])
		{
			vis[v]=1;
			if(cy[v]==0||path(cy[v]))
			{
				cy[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int MaxMatch()
{
	int sum=0;
	memset(cy,0,sizeof(cy));
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		sum+=path(i);
	}
	return sum;
}

int main()
{
	int i,j,a;
	while(scanf("%d",&n),n)
	{
		memset(e,0,sizeof(e));
		scanf("%d",&m);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
		{
			scanf("%d",&a);
			if(a==1)
				e[i][j]=1;
		}
		ans=MaxMatch();
		printf("%d\n",ans);
	}
}