二分图匹配的H-K算法

        算法的具体描述请看http://chenhaifeng.blog.edu.cn/2007/91117.html，我只是来贴代码的。

        http://blog.csdn.net/emoizhang/article/details/8004502这里讲的比我详细（虽然都是废话），但他的代码比我的慢。

【题目描述】

给一个有向无环图，求最小链覆盖

【输入格式】

第一行两个数n、m，分别表示地图的点数和边数，接下来m行，每行两个数u、v,表示有一条从点u到点v的有向边。

【数据范围】

n<=200000,m<=500000

【题解】

将每个点拆成两个点，求最大匹配，答案即为点数减去最大匹配数。由于数据很大，所以需要使用HK算法。
Code：

program maze;
type
        int=longint;
var
        i,j,k,m,n,x,y,tot,ans,l,r:int;
        ne,t:array[1..500100]of int;
        h,link,d,q:array[1..401000]of int;
        visited,v:array[1..201000]of boolean;

procedure prepare;
begin
        for i:=1 to n do begin
                j:=h[i];
                while j<>0 do begin
                        k:=t[j];
                        if link[k]=0 then begin
                                link[k]:=i;inc(ans);
                                v[i]:=true;break;
                        end;
                        j:=ne[j];
                end;
        end;
end;

function bfs:boolean;
begin
        fillchar(d,sizeof(d),$FF);
        l:=0;r:=0;bfs:=false;
        for i:=1 to n do if not v[i]then begin
                d[i]:=0;inc(r);q[r]:=i;
        end;
        if l=r then exit;
        repeat
                inc(l);i:=q[l];j:=h[i];
                while j<>0 do begin
                        k:=t[j];m:=link[k];
                        if m=0 then bfs:=true
                        else if d[m]=-1 then begin
                                d[m]:=d[i]+1;inc(r);q[r]:=m;
                        end;
                        j:=ne[j];
                end;
        until l=r;
end;

function dfs(x:int):boolean;
var j,k:int;
begin
        j:=h[x];
        while j<>0 do begin
                k:=t[j];
                if(link[k]=0)or((d[link[k]]=d[x]+1)and(dfs(link[k])))then begin
                        link[k]:=x;exit(true);
                end;
                j:=ne[j];
        end;
        exit(false);
end;

begin
        assign(input,'maze.in');reset(input);
        assign(output,'maze.out');rewrite(output);
        read(n,m);
        for i:=1 to m do begin
                read(x,y);
                inc(tot);t[tot]:=y+n;
                ne[tot]:=h[x];h[x]:=tot;
        end;
        ans:=0;
        prepare;
        while bfs do
                for i:=1 to n do if(not v[i])and(dfs(i))then begin
                        v[i]:=true;inc(ans);
                end;
        write(n-ans);
        close(input);close(output);
end.

在具体的实现时，我先贪心了一个初始匹配（prepare），稍微加快了一点速度。