题解：P3386 【模板】二分图最大匹配

匈牙利算法

我们用一个二维数组来存图，然后遍历

n

个节点，看看这

n

个点中，有多少个可以连。

核心代码

CPP

bool dfs(int u) {
	for (int i = 1; i <= m; i++) {
		if (f[u][i] && !vis[i]) {
			vis[i] = 1;
			if (!match[i] || dfs(match[i])) {
				match[i] = u;
				return 1;
			}
		}
	}
	return 0;
}

遍历

m

条边，看看那些边跟

u

联系上了，接着看当前节点有没有被连上，如果没有，更新访问数组。接下来看当前节点的匹配节点是什么，如果没有，那么把匹配节点设成

u

；如果有，尝试把它连得点断掉，把当前节点匹配上

u

。

代码

CPP

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>

using namespace std;

const int N = 1e3;
bool f[N][N];
bool vis[N];
int match[N], n, m, e; 

bool dfs(int u) {
	for (int i = 1; i <= m; i++) {
		if (f[u][i] && !vis[i]) {
			vis[i] = 1;
			if (!match[i] || dfs(match[i])) {
				match[i] = u;
				return 1;
			}
		}
	}
	return 0;
}

int main() {
	scanf("%d%d%d", &n, &m, &e);
	for (int i = 1; i <= e; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		f[x][y] = 1;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		if (dfs(i)) ans++;
	}
	printf("%d\n", ans);
	return 0;
}

题解：P3386 【模板】二分图最大匹配

文章操作

匈牙利算法

核心代码

代码

相关推荐

评论

题解：P3386 【模板】二分图最大匹配