vijos 1204 CoVH之柯南开锁

　

柯南h

背景Background

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

描述Description

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

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

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

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

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

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

输入格式Input Format  

  第一行 两个不超过100的正整数N, M表示矩阵的长和宽

以下N行 每行M个数 非0即1 1为凸起方格  

输入样例:

4 4

0000

0101

0000

0100

输出样例：

2

思路：

最小覆盖问题：

给定一个二分图，求最小的点数，使得每一条边都至少与一个顶点相邻。

solution：

可以证明：二分图最小覆盖数=最大匹配数。

证明：

假设最大匹配边数为M

1.M是足够的。因为如果存在边E未与顶点相连，则E可以匹配，此时不是最大匹配。

2.M是必须的。仅考虑构成最大匹配的M条边，他们两两无公共点，所以需要M个顶点覆盖他们。

看不懂？好吧。简而言之，对于i行j列有按钮的格子连边i->j，然后求最大匹配数。

源代码/pas：

type
  arr=record
    x,y,w:longint;
    next:longint;
end;

var
  a:array[1..10000] of arr;
  v:array[1..30000] of boolean;
  st,ls:array[1..30000] of longint;
  i,j:longint;
  n,m,nm:longint;
  k:char;

function find(r:longint):boolean;
var
  i,j,k:longint;
begin
  find:=true;
  i:=ls[r];
  while i<>0 do
    begin
      with a[i] do
        if not v[y]
          then
            begin
              k:=st[y]; st[y]:=r; v[y]:=true;
              if (k=0) or find(k) then exit;
              st[y]:=k;
            end;
      i:=a[i].next;
    end;
  find:=false;
end;

procedure main;
var
  i,j,k:longint;
  z:boolean;
begin
  for i:=1 to n do
    begin
      fillchar(v,sizeof(v),0);
      z:=find(i);  
    end;
end;

begin      
  readln(n,m);
  nm:=0;
  for i:=1 to n do
    begin
      for j:=1 to m do
        begin
          read(k);
          if k='1' then begin
          nm:=nm+1;
          with a[nm] do
            begin
              x:=i;
              y:=n+j;
              next:=ls[x];
              ls[x]:=nm;
            end;
          end;
        end;
      readln;
    end;
  main;
  j:=0;
  for i:=n to n+m do
    if st[i]<>0 then j:=j+1;
  write(j);
end.

相关阅读