pku3041 Asteroids

给一个n*n的矩阵，其中有一些坏东西需要消灭，用激光炮每次消灭一行或一列中的所有坏东西，问最少次数。

总结一下，对于每个坏东西，我们有两种方案消灭它，横着打或者竖着打，满足最小覆盖的定义，

用方案做点（即每个坏东西的x坐标和y坐标），连边求最大匹配OK

View Code

 1 program pku3041(input,output);
 2 var
 3    f   : array[0..1100,0..1100] of boolean;
 4    v   : array[0..1100] of boolean;
 5    lk  : array[0..1100] of longint;
 6    n,m : longint;
 7 procedure init;
 8 var
 9    i,xx,yy : longint;
10 begin
11    fillchar(f,sizeof(f),false);
12    readln(n,m);
13    for i:=1 to m do
14    begin
15       readln(xx,yy);
16       f[xx,yy+n]:=true;
17    end;
18 end; { init }
19 function find(now :longint ):boolean;
20 var
21    i : longint;
22 begin
23    for i:=n+1 to n+n do
24       if (not v[i])and(f[now,i]) then
25       begin
26      v[i]:=true;
27      if (lk[i]=0)or(find(lk[i])) then
28      begin
29         lk[i]:=now;
30         exit(true);
31      end;
32       end;
33    exit(false);
34 end; { find }
35 function main:longint;
36 var
37    i : longint;
38 begin
39    main:=0;
40    for i:=1 to n do
41    begin
42       fillchar(v,sizeof(v),false);
43       if find(i) then
44      inc(main);
45    end;
46 end; { main }
47 begin
48    while not eof do
49    begin
50       init;
51       writeln(main);
52    end;
53 end.