C++

二分图


// eft
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4+100;

int n, m, t, res;
int vis[N], mch[N];

struct Edge {int frm, to, nxt;}e[N<<3]; int cnt, h[N<<3]; 

inline void add_edge (int u, int v) {
	e[++cnt].nxt = h[u], h[u] = cnt;
	e[cnt].frm = u, e[cnt].to = v;
}

inline int dfs (int x) {
	for (int i = h[x]; i; i = e[i].nxt) {
		int y = e[i].to;
		if (vis[y]) continue;
		vis[y] = 1;
		if (!mch[y] || dfs (mch[y])) {
			mch[y] = x;
			return 1;
		}
	}
	return 0;
}

main () {
	cin >> n >> m >> t;
	for (int i = 1, u, v; i <= t; ++ i) {
		scanf ("%d%d", &u, &v);
		if (u > n || v > m) continue;
		add_edge (u, v);
	}
	for (int i = 1; i <= n; ++ i) {
		memset (vis, 0, sizeof vis);
		if (dfs (i)) ++ res;
	}
	cout << res;
	return 0;
}

PS:

1."if" must special judgement

2.the important thought is:

first.use the U to match V

second. if the V has matched w

third. dfs(w) if we get true,thus the U --> V; else we need to find the other edge of the U


作者:凤源,发布于:2020/07/23
原文:https://www.cnblogs.com/yszhyhm/p/13365601.html