【图论】二分图匹配(Hungary算法&KM算法&hopcroft-karp算法)

易橙

于 2020-04-06 20:38:37 发布

阅读量593

点赞数 1

分类专栏：图论

本文链接：https://blog.csdn.net/Rainfoo/article/details/105350722

版权

本文深入探讨了二分图匹配问题，包括匈牙利算法的邻接表实现，KM算法的O(n^3)复杂度解法，以及Hopcroft-Karp算法的平方根优化策略。这些算法在解决匹配问题时具有不同的效率和理解难度，适合不同层次的学习者。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

匈牙利算法板子(用邻接表写可以做到O(n*m))：

const int maxn = 510;
int cnt_x,cnt_y;
int G[maxn][maxn];
int link[maxn];
bool vis[maxn];

bool find(int u){
   
    for(int v=1;v<=cnt_y;v++){
   
        if(G[u][v]&&!vis[v]){
   
            vis[v]=true;
            if(link[v]==-1||find(link[v])){
   
                link[v]=u;
                return true;
            }
        }
    }
    return false;
}

int Hungary(){
   
    int ans=0;
    memset(link,-1,sizeof(link));
    for(int u=1;u<=cnt_x;u++){
   
        memset(vis,0,sizeof(vis));
        if(find(u)) ans++;
    }
    return ans;
}

KM算法の O(n^3)的板子：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define mem(a) memset(a,0,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=1e3+7;
int wx[maxn],wy[maxn];
int cx[maxn],cy[maxn];
int visx[maxn],visy[maxn];
int cntx,cnty;
int Map[maxn][maxn];
int slack[maxn];
bool find(int u){
   
	visx[u]=1;
	for(int v=1;v<=cnty;v++){
   
		if(!visy[v]&&Map[u][v]!=INF){
   
			int t=wx[u]+wy[v]-Map[u][v];
			if(t==0){
   
				visy[v]=1;
				if(cy[v]==-1||find(cy[v])){
   
					cx[u]=v;
					cy[v]=u;
					return true;
				}
			}
			else if(t>0)

最低0.47元/天解锁文章