Hopcroft-Karp算法 poj-1469 COURSES

「爱情、让人受尽委屈。」 2022-11-27 15:52 98阅读 0赞

##### Hopcroft-karp算法 #####

该算法由John.E.Hopcroft和Richard M.Karp于1973提出，故称Hopcroft-Karp算法。

##### 使用情形 #####

给定一个二分图，求其最大匹配。

##### 原理简述 #####

在增广匹配集时，每次寻找多条增广路径，以进一步减少时间复杂度。

##### 步骤及示例演示 #####

dx【】、dy【】  
分别表示二分图左右不顶点的距离标号

mx【】、my【】  
分别表示二分图左右部顶点的距离标号

1、我们每次从所有未匹配的左部节点开始BFS，进行距离标号。

2、对于每一个队列中的左部节点X，考虑与它相邻的所有右部节点Y：

2.1、如果Y是一个未匹配的右部节点，则说明至少还存在一条增广路，用一个bool变量flag记录，以便之后增广。

2.2、否则，将Y的匹配节点加入到队列中。顺便求出距离标号。

3、当BFS结束时，

3.1、若不存在增广路（flag==false），那么算法结束；

3.2、否则，对于每一个没有匹配的左部节点X执行匈牙利算法find(x)的操作。

4、这里，find（x）过程中，只考虑边（u,v）：满足dx【u】+1==dy【v】。

##### 与其他算法的区别于联系 #####

Hopcroft-karp算法，相比于普通的匈牙利算法来说，由于每次是增广一系列路径，所以更快，算法复杂度降低了(n^0.5)

##### 题目链接 [点击这里][Link 1] #####

##### 代码 #####

#include <cstdio>
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <cstring>
    
    using namespace std;
    
    const int max_n=300;
    const int max_p=300;
    
    int n,p;
    
    vector<int> g[max_p+1];
    // mx,my表示二分图左右顶点的匹配节点
    int mx[max_p+1],my[max_n+1];
    queue<int> que;
    // dx,dx表示二分图左右顶点的距离标号
    int dx[max_p+1],dy[max_n+1];
    bool vis[max_p+1];
    
    
    bool find(int u)
    {
        
        for(int i=0;i<g[u].size();++i)
        {
        
            int v=g[u][i];
            if(!vis[v] && dy[v]==dx[u]+1)
            {
        
                vis[v]=true;
                if(!my[v] || find(my[v]))
                {
        
                    mx[u]=v;
                    my[v]=u;
                    return true;
                }
            }
        }
        return false;
    }
    
    int matching()
    {
        
        // 初始化mx，my，ans；
        memset(mx,0,sizeof(mx));
        memset(my,0,sizeof(my));
        int ans=0;
        while(true)
        {
        
            // 初始化flag，队列que，dx,dy;
            bool flag=false;
            while(!que.empty())
            {
        
                que.pop();
            }
            memset(dx,0,sizeof(dx));
            memset(dy,0,sizeof(dy));
    
            // 将没有匹配的x的编号，加入到队列中
            for(int i=1;i<=p;++i)
            {
        
                if(!mx[i])
                {
        
                    que.push(i);
                }
            }
    
            // 如果还有未曾匹配的x
            while(!que.empty())
            {
        
                // 选取一个未曾匹配的x
                int u=que.front();
                que.pop();
                for(int i=0;i<g[u].size();++i)
                {
        
                    int v=g[u][i];
                    //如果y距离未曾设置
                    if(!dy[v])
                    {
        
                        // 设置距离判断条件,dy[v]是dx[u]的下一个匹配点
                        dy[v]=dx[u]+1;
                        if(my[v])
                        {
        
                            dx[ my[v] ] = dy[v] +1;
                            que.push(my[v]);
                        }
                        else
                        {
        
                            flag=true;
                        }
                    }
                }
            }
    
            if(!flag)
            {
        
                break;
            }
    
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=p;++i)
            {
        
                if(!mx[i] && find(i))
                {
        
                    ans++;
                }
            }
        }
        return ans;
    }
    
    
    int main()
    {
        
        int T;
        scanf("%d",&T);
        while(T--)
        {
        
            scanf("%d %d",&p,&n);
            for(int i=1;i<=p;++i)
            {
        
                int cnt,k;
                scanf("%d",&cnt);
                for(int j=0;j<cnt;++j)
                {
        
                    scanf("%d",&k);
                    g[i].push_back(k);
                }
            }
    
            int ans=matching();
            if(ans==p)
            {
        
                printf("YES\n");
            }
            else
            {
        
                printf("NO\n");
            }
    
            // 记得清空vector容器
            // 第一次写的时候，忘记清空容器了，导致发生了错误，又找不到算法的问题
            // 花费了很多时间
            for(int i=1;i<=n;++i)
            {
        
                g[i].clear();
            }
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1469