登录
← 返回首页 | 代码片段 › 3 图论 › 3.4 二分图与最大匹配 › 二分图与最大匹配 / 搜索
JSON MD

3.4 二分图与最大匹配

二分图最大匹配-匈牙利算法 erfentu
34 行
CPP JSON
【二分图最大匹配——匈牙利算法(Hungarian Algorithm)】 ▪ main() — 读入左右部节点数 n1,n2 和边数 m,用 lambda 递归 DFS 寻找增广路 ▪ dfs(self, x) — 嵌套 DFS:对左部节点 x 尝试匹配,遍历其所有邻接右部节点 y:若 y 未被访问且(y 未匹配 或 y 的当前匹配者可换人),则 match[y]=x 并返回 true ▪ vis[] — 每轮 DFS 的访问标记数组,防止重复访问右部节点 ▪ match[] — 右部节点当前的匹配对象(0 表示未匹配) 时间复杂度 O(VE)。适用于任务分配、人员配对、棋盘多米诺覆盖等二分图匹配模型。
C++ 34 行 CPP
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n1,n2,m;
    cin >> n1 >> n2 >> m;
    vector<vector<int>>ver(n1+1);
    for(int i = 1;i <= m;i++){
        int x,y;
        cin >> x >> y;
        ver[x].push_back(y);
    }

    int ans = 0;
    vector<int>match(n2+1);
    for(int i = 1;i <= n1;i++){
        vector<int>vis(n2+1);
        auto dfs = [&](auto self,int x) -> bool {
            for(auto y : ver[x]){
                if(vis[y])continue;
                vis[y] = 1;
                if(!match[y] || self(self,match[y])){
                    match[y] = x;
                    return true;
                }
            }
            return false;
        };
        if(dfs(dfs,i)){
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}
二分图—最大匹配 add
36 行
CPP JSON
【二分图—最大匹配】 二分图匹配算法模板(匈牙利算法 / Hopcroft-Karp)。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 int dfs(Re x) — 深度优先搜索遍历 核心结构体:QAQ 关键配置: N=1003 适用场景:二分图判定与匹配、棋盘覆盖模型、最小点覆盖
C++ 35 行 CPP
#include<cstring>
#include<cstdio>
#define Re register int
const int N=1003;
int o,n,m,e,x,y,ans,pan[N],head[N],match[N];
struct QAQ{int to,next;}a[N*N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline int dfs(Re x){
	for(Re i=head[x],to;i;i=a[i].next)
		if(!pan[to=a[i].to]){
			pan[to]=1;
			if(!match[to]||dfs(match[to])){
				match[to]=x;return 1;
			}
		}
	return 0;
}
int main(){
	in(n),in(m),in(e);
	while(e--){
		in(x),in(y);
		if(x<=n&&y<=m)add(x,y);
	}
	for(Re i=1;i<=n;++i){
		memset(pan,0,sizeof(pan));
		ans+=dfs(i);
	}
	printf("%d",ans);
}
二分图判定 染色法
40 行
CPP JSON
【二分图判定(染色法)】 二分图匹配算法模板(匈牙利算法 / Hopcroft-Karp)。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 int judge(无参数) — 判定函数 核心结构体:QAQ 关键配置: N=2003,M=1e6+3 适用场景:二分图判定与匹配、棋盘覆盖模型、最小点覆盖
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=2003,M=1e6+3;
int n,m,x,y,h,t,o,T,O,Q[N],head[N],color[N];
struct QAQ{int to,next;}a[M<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int judge(){
	for(Re i=1;i<=n;++i)
		if(!color[i]){
			h=1,t=0,Q[++t]=i,color[i]=1;
			while(h<=t){
				Re x=Q[h++];
				for(Re j=head[x],to;j;j=a[j].next)
					if(!color[to=a[j].to])color[to]=3-color[x],Q[++t]=to;
					else if(color[to]==color[x])return 0;
			}
		}
	return 1;
}
int main(){
	in(T);
	while(T--){
		memset(color,0,sizeof(color));
		memset(head,0,sizeof(head));
		in(n),in(m),o=0;
		while(m--)in(x),in(y),add(x,y),add(y,x);
		printf("Scenario #%d:\n",++O);
		puts(judge()?"No suspicious bugs found!\n":"Suspicious bugs found!\n");
	}
}
已复制