[Vijos1204] CoVH 之柯南开锁

2014-11-26
竞赛题解 / 图论
Vijos二分图

背景 Background

随着时代的演进, 困难的刑案也不断增加…

但真相只有一个

虽然变小了, 头脑还是一样好, 这就是名侦探柯南!

描述 Description

[CoVH06]

面对 OIBH 组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实.

他经过深思熟虑, 决定从 OIBH 组织大门进入………..

OIBH 组织的大门有一个很神奇的锁.

锁是由 M*N 个格子组成, 其中某些格子凸起 (灰色的格子). 每一次操作可以把某一行或某一列的格子给按下去.

如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是 OIBH 组织不是吃素的, 他们的限定次数恰是最少次数.

请您帮助柯南计算出开给定的锁所需的最少次数.

输入格式 InputFormat

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

输出格式 OutputFormat

一个整数 所需最少次数

样例输入 SampleInput

4 4
0000
0101
0000
0100

样例输出 SampleOutput

2

Vijos 1204

代码 Code

对于每个凸起的格子，以横纵坐标建边，求最小顶点覆盖（最大匹配）。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=105;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
    int to,nx,vl;
}e[maxn*maxn];
int head[maxn],match[maxn];
bool used[maxn];
int cnt,mat;
char ch[maxn];
inline void ins(int u,int v)
{
    e[++cnt].to=v;e[cnt].nx=head[u];
    head[u]=cnt;
}
bool crosspath(int s)
{
    int i,j,t,u,v,w;
    for (i=head[s];i;i=e[i].nx)
    {
        v=e[i].to;
        if (!used[v])
        {
            used[v]=true;
            if (!match[v] || crosspath(match[v]))
            {
                match[v]=s;
                return true;
            }
        }
    }
    return false;
}
inline void hungary()
{
    int i,j,t;
    for (i=1;i<=n;i++)
    {
        memset(used,false,sizeof(used));
        if (crosspath(i)) mat++;
    }
}
int main()
{
    mat=cnt=0;
    memset(match,0,sizeof(match));
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%s",ch);
        for (j=0;j<m;j++) if (ch[j]=='1') ins(i,j+1);
    }
    hungary();
    printf("%d\n",mat);
    return 0;
}