匈牙利算法模板

匈牙利算法模板

#include #include #include #include using namespace std;const int maxn = 100;int n1, n2, m;bool vis[maxn];int match[maxn];vector G[maxn];bool dfs(int u) { for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (vis[v]) continue; vis[v] = true; if (match[v] == 0 || dfs(match[v])) { match[v] = u; return true; } } return false;}int main() { scanf("%d %d %d", &n1, &n2, &m); for (int i = 0; i <= n1; i++) G[i].clear(); for (int i = 0; i <= n2; i++) match[i] = 0; int ans = 0; for (int i = 1; i <= n1; i++) { for (int j = 0; j <= n2; j++) vis[i] = false; if (dfs(i)) ans++; } printf("%d\n", ans);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。