Vijos P1204 CoVH之柯南开锁

题目

背景

随着时代的演进,困难的刑案也不断增加…
但真相只有一个
虽然变小了,头脑还是一样好,这就是名侦探柯南!
描述

[CoVH06]
面对OIBH组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实.
他经过深思熟虑, 决定从OIBH组织大门进入………..
OIBH组织的大门有一个很神奇的锁.
锁是由M*N个格子组成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子给按下去.
图片
如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是OIBH组织不是吃素的, 他们的限定次数恰是最少次数.
请您帮助柯南计算出开给定的锁所需的最少次数.
格式

输入格式

第一行两个不超过100的正整数N, M表示矩阵的长和宽
以下N行每行M个数非0即1 1为凸起方格
输出格式

一个整数所需最少次数
样例1

样例输入1

样例输出1

限制

全部1秒
提示

OIBH组织的第一道防线居然被柯南突破了. 这引起了OIBH组织的高度重视, 他们派出了黄金十二人+青铜五小强进行抵抗.

题解

二分图匈牙利算法

代码

#include<cstdio>
#include<cstring>
using namespace std;int n,m,tot,ans;
int lnk[105],s[105];
bool vis[105];
char ch;
struct edge
{int nxt,y;
} e[20005];void add(int x,int y)
{tot++;e[tot].nxt=lnk[x];lnk[x]=tot;e[tot].y=y;
}int dfs(int x)
{for (int i=lnk[x];i;i=e[i].nxt){if (vis[e[i].y]==false) {vis[e[i].y]=true;if (!s[e[i].y]||dfs(s[e[i].y])){s[e[i].y]=x;return true;}}}return false;
}int main()
{scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){ch=getchar();while (ch<'0'||ch>'9') ch=getchar();if (ch=='1') add(i,j);}memset(s,0,sizeof(s));for (int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if (dfs(i)) ans++;}printf("%d",ans);return 0;
}