二分匹配HK算法

#define nn 21000 //两边的点数均为nn
int nx,ny;//建图时左边点从0到nx-1,右边点从nx到nx+ny-1
int cx[nn],cy[nn];
int dx[nn],dy[nn];
int dis;
bool bmask[nn];//记录右边是否匹配
bool searchpath()
{
    queue<int>q;
    dis=INF;
    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    REP(i,nx)
    {
        if(cx[i]==-1)
        {
            q.push(i);
            dx[i]=0;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(dx[u]>dis) break;

        for(int p=head[u]; p!=-1; p=edge[p].next)
        {
            int to=edge[p].to-nx;
            if(dy[to]==-1)
            {
                dy[to]=dx[u]+1;
                if(cy[to]==-1) dis=dy[to];
                else
                {
                    dx[ cy[to] ]=dy[to]+1;
                    q.push(cy[to]);
                }
            }
        }
    }
    return dis!=INF;
}

int find(int u)
{
    for(int p=head[u]; p!=-1; p=edge[p].next)
    {
        int to=edge[p].to-nx; //右边点要剪掉nx
        if(!bmask[to] && dy[to]==dx[u]+1)
        {
            bmask[to]=1;
            if(cy[to]!=-1 && dy[to]==dis) continue;
            if(cy[to]==-1 || find(cy[to]))
            {
                cy[to]=u;
                cx[u]=to;
                return 1;
            }
        }
    }
    return 0;
}

int match()
{
    memset(cx,-1,sizeof(cx));
    memset(cy,-1,sizeof(cy));
    int ret=0;
    while(searchpath())
    {
        memset(bmask,0,sizeof(bmask));
        REP(i,nx)
        {
            if(cx[i]==-1)   ret+=find(i);
        }
    }
    return ret;
}