背景 Background
随着时代的演进,困难的刑案也不断增加...但真相只有一个虽然变小了,头脑还是一样好,这就是名侦探柯南!
描述 Description
面对OIBH组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实.他经过深思熟虑, 决定从OIBH组织大门进入...........
OIBH组织的大门有一个很神奇的锁.锁是由M*N个格子组成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子给按下去.
如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是OIBH组织不是吃素的, 他们的限定次数恰是最少次数.
请您帮助柯南计算出开给定的锁所需的最少次数.
输入格式 Input Format
第一行 两个不超过100的正整数N, M表示矩阵的长和宽
以下N行 每行M个数 非0即1 1为凸起方格
输出格式 Output Format
一个整数 所需最少次数
样例输入 Sample Input
4 4
0000
0101
0000
0100
样例输出 Sample Output
2
时间限制 Time Limitation
全部1秒
分析：
仔细看题后发现就是求二分图最小覆盖点集，可以用“匈牙利算法”解决，因为二分图最小覆盖点集==最大匹配数.
证明：matrix67博客 http://www.matrix67.com/blog/archives/116
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int link[110];
bool g[110][110],vis[110];
int n,m,ans;
bool Find(int now)
{
for (int i=1;i<=m;i++)
if (!vis[i] && g[now][i])
{
vis[i]=true;
if (link[i]==0 || Find(link[i]))
{
link[i]=now;
return true;
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m); getchar();
memset(g,false,sizeof(g));
char c;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
scanf("%c",&c);
if (c=='1') g[i][j]=true;
}
getchar();
}
memset(link,0,sizeof(link));
ans=0;
for (int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if (Find(i)) ans++;
}
printf("%d\n",ans);
return 0;
}