About二分图

参考博客 by ling_wang参考博客 by Matrix67

模板题 luogu3386

luogu3386 二分图匹配 の 传送门

这里是 匈牙利算法 Code

#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; const int N = 1007, M = 1007; int n, m, e, cnt, ans, nxt[N * M], to[N * M], head[N], ch[1010]; bool vis[1010]; inline int read(){ int ans = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') ans = (ans << 3) + (ans << 1) + ch - 48, ch = getchar(); return ans * f; } void add(int u, int v){ nxt[++cnt] = head[u]; to[cnt] = v; head[u] = cnt; } bool dfs(int k){ for (int i = head[k]; i; i = nxt[i]){ int v = to[i]; if (!vis[v]){ vis[v] = true; if (!ch[v] || dfs(ch[v])){ ch[v] = k; return true; } } } return false; } int main(){ //freopen("testdata.in.txt", "r", stdin); n = read(), m = read(), e = read();; for (int i = 1; i <= e; ++i){ int x = read(), y = read(); if (x <= n && y <= m) add(x, y); } ans = 0; for (int i = 1; i <= n; i++){ memset(vis, false, sizeof(vis)); if (dfs(i)) ans++; //else printf("%d\n", i); } printf("%d\n", ans); return 0; }

转载于:https://www.cnblogs.com/DorkyTAT/p/11160706.html