实现功能为二分图匹配
原理:匈牙利算法,核心思想——匹配上了就配,没直接匹配上也要通过前面的腾出位置让这个匹配上(详见:趣写算法系列之——匈牙利算法)
本程序以Codevs2776为例
1 type
2 point=^node;
3 node=record
4 g:longint;
5 next:point;
6 end;
7 var
8 i,j,k,l,m,n:longint;
9 c,f:array[0..1000] of longint;
10 a:array[0..1000] of point;
11 procedure add(x,y:longint);inline;
12 var p:point;
13 begin
14 new(p);
15 p^.g:=y;
16 p^.next:=a[x];
17 a[x]:=p;
18 end;
19 function check(x:longint):boolean;inline;
20 var p:point;
21 begin
22 p:=a[x];
23 while p<>nil do
24 begin
25 if f[p^.g]<>i then
26 begin
27 f[p^.g]:=i;
28 if c[p^.g]=0 then
29 begin
30 c[p^.g]:=x;
31 exit(true);
32 end
33 else if check(c[p^.g]) then
34 begin
35 c[p^.g]:=x;
36 exit(true);
37 end;
38 end;
39 p:=p^.next;
40 end;
41 exit(false);
42 end;
43
44 {$IFDEF WINDOWS}{$R wiki2776.rc}{$ENDIF}
45
46 begin
47 readln(n,m);
48 for i:=1 to n do
49 begin
50 a[i]:=nil;
51 while not(eoln) do
52 begin
53 read(j);
54 if j=0 then break;
55 add(i,j);
56 end;
57 readln;
58 end;
59 fillchar(c,sizeof(c),0);
60 fillchar(f,sizeof(f),0);l:=0;
61 for i:=1 to n do
62 if check(i) then inc(l);
63 writeln(l);
64 readln;
65 end.
66