uoj#78. 二分图最大匹配

 1 program rrr(input,output);
 2 const
 3   inf=123456789;
 4 type
 5   etype=record
 6      t,c,next,rev:longint;
 7   end;
 8 var
 9   e:array[0..600000]of etype;
10   a,cur,d:array[-550..550]of longint;
11   q:array[0..1100]of longint;
12   l,r,i,x,y,j,m,cnt,ans,h,t:longint;
13 function min(a,b:longint):longint;
14 begin
15    if a<b then exit(a) else exit(b);
16 end;
17 procedure ins(x,y,c:longint);
18 begin
19    inc(cnt);e[cnt].t:=y;e[cnt].c:=c;e[cnt].next:=a[x];a[x]:=cnt;
20 end;
21 procedure add(x,y,c:longint);
22 begin
23    ins(x,y,c);e[cnt].rev:=cnt+1;ins(y,x,0);e[cnt].rev:=cnt-1;
24 end;
25 procedure bfs;
26 begin
27    for i:=-l to r+1 do d[i]:=-1;d[0]:=0;
28    h:=0;t:=1;q[1]:=0;
29    while h<t do
30       begin
31          inc(h);
32          i:=a[q[h]];
33          while i<>0 do
34             begin
35                if (d[e[i].t]=-1) and (e[i].c>0) then
36                   begin
37                      d[e[i].t]:=d[q[h]]+1;
38                      inc(t);q[t]:=e[i].t;
39                   end;
40                i:=e[i].next;
41             end;
42       end;
43 end;
44 function dfs(k,f:longint):longint;
45 var
46   ans,t,i:longint;
47 begin
48    if (k=r+1) or (f=0) then exit(f);
49    ans:=0;i:=cur[k];
50    while i<>0 do
51       begin
52          if (d[e[i].t]=d[k]+1) and (e[i].c>0) then
53             begin
54                t:=dfs(e[i].t,min(f,e[i].c));
55                dec(e[i].c,t);inc(e[e[i].rev].c,t);
56                inc(ans,t);dec(f,t);
57                if f=0 then break;
58             end;
59          i:=e[i].next;cur[k]:=i;
60       end;
61    if f>0 then d[k]:=-1;
62    exit(ans);
63 end;
64 begin
65    assign(input,‘r.in‘);assign(output,‘r.out‘);reset(input);rewrite(output);
66    readln(l,r,m);
67    fillchar(a,sizeof(a),0);cnt:=0;
68    for i:=1 to l do add(0,-i,1);
69    for i:=1 to m do begin readln(x,y);add(-x,y,1); end;
70    for i:=1 to r do add(i,r+1,1);
71    ans:=0;
72    while true do
73       begin
74          bfs;
75          if d[r+1]=-1 then break;
76          for i:=-l to r+1 do cur[i]:=a[i];
77          ans:=ans+dfs(0,inf);
78       end;
79    writeln(ans);
80    for i:=1 to l do
81       begin
82          j:=a[-i];
83          while j<>0 do begin if e[j].c=0 then break;j:=e[j].next; end;
84          if j=0 then write(0,‘ ‘) else write(e[j].t,‘ ‘);
85       end;
86    close(input);close(output);
87 end.