必威体育Betway必威体育官网
当前位置:首页 > IT技术

vijos 1204 CoVH之柯南开锁

时间:2019-08-12 06:14:17来源:IT技术作者:seo实验室小编阅读:66次「手机版」
 

柯南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.

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读