2013-team4/code/Hopcroft-Karp

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
Hopcroft_Karp算法采用了类似dinic的算法，给节点分层标号。时间复杂度为O(sqrt(V)*E) （传说dinic求最大匹配也可以做到这个复杂度。。。。）
说明：图用邻接表储存，MX[]表示X集合匹配的位置，MY[]表示Y集合匹配的位置，LX[]表示X集合节点的标号，LY[]表示Y集合节点的标号
}}}
{{{
vector<int> E[MAXN];
int MX[MAXN], MY[MAXN];
int LX[MAXN], LY[MAXN];
int que[MAXN];
int N, M;

bool bfs()
{
    int front=0, rear=1, flag=0;
    memset(LX, -1, sizeof(LX));
    memset(LY, -1, sizeof(LY));
    for (int i=1; i<=N; i++) 
        if (MX[i]==-1) que[rear++]=i, LX[i]=0;
    for (; front<rear; front++)
    {
        int u=que[front];
        for (int i=0; i<E[u].size(); i++)
        {
            int v=E[u][i]; if (LY[v]>=0) continue;
            LY[v]=LX[u]+1;
            if (MY[v]==-1) flag=1;
            else LX[MY[v]]=LY[v]+1, que[rear++]=MY[v];
        }
    }
    return flag;
}

bool find(int u)
{
    for (int i=0; i<E[u].size(); i++)
    {
        int v=E[u][i]; if (LY[v]!=LX[u]+1) continue;
        LY[v]=-1;
        if (MY[v]==-1||find(MY[v]))
        {
            MY[v]=u; MX[u]=v;
            return true;
        }
    }
    return false;
}

int Hopcroft_Karp()
{
    memset(MX, -1, sizeof(MX));
    memset(MY, -1, sizeof(MY));
    int maxmatch=0;
    while (bfs())
    {
        for (int i=1; i<=N; i++)
            if (MX[i]==-1&&find(i)) maxmatch++;
    }
    return maxmatch;
}
}}}

Hopcroft_Karp算法采用了类似dinic的算法，给节点分层标号。时间复杂度为O(sqrt(V)*E) （传说dinic求最大匹配也可以做到这个复杂度。。。。）
说明：图用邻接表储存，MX[]表示X集合匹配的位置，MY[]表示Y集合匹配的位置，LX[]表示X集合节点的标号，LY[]表示Y集合节点的标号

vector<int> E[MAXN];
int MX[MAXN], MY[MAXN];
int LX[MAXN], LY[MAXN];
int que[MAXN];
int N, M;
bool bfs()
{
    int front=0, rear=1, flag=0;
    memset(LX, -1, sizeof(LX));
    memset(LY, -1, sizeof(LY));
    for (int i=1; i<=N; i++) 
        if (MX[i]==-1) que[rear++]=i, LX[i]=0;
    for (; front<rear; front++)
    {
        int u=que[front];
        for (int i=0; i<E[u].size(); i++)
        {
            int v=E[u][i]; if (LY[v]>=0) continue;
            LY[v]=LX[u]+1;
            if (MY[v]==-1) flag=1;
            else LX[MY[v]]=LY[v]+1, que[rear++]=MY[v];
        }
    }
    return flag;
}
bool find(int u)
{
    for (int i=0; i<E[u].size(); i++)
    {
        int v=E[u][i]; if (LY[v]!=LX[u]+1) continue;
        LY[v]=-1;
        if (MY[v]==-1||find(MY[v]))
        {
            MY[v]=u; MX[u]=v;
            return true;
        }
    }
    return false;
}
int Hopcroft_Karp()
{
    memset(MX, -1, sizeof(MX));
    memset(MY, -1, sizeof(MY));
    int maxmatch=0;
    while (bfs())
    {
        for (int i=1; i<=N; i++)
            if (MX[i]==-1&&find(i)) maxmatch++;
    }
    return maxmatch;
}