The Accomodation of Students 二分图判定+匹配

The Accomodation of Students 二分图判定+匹配

模板题，复习一下模板

#include #include #include #include using namespace std;const int maxn = 205;int n, m, tot, head[maxn], vis[maxn], match[maxn];struct Edge { int to, next; } edges[maxn*maxn];void init() { tot = 0; memset(head, -1, sizeof(head)); }void addedge(int u, int v) { edges[++tot].to = v; edges[tot].next = head[u]; head[u] = tot;}bool dfs(int u) { for (int i = head[u]; ~i; i = edges[i].next) { int v = edges[i].to; if (vis[v]) { if (vis[v] == -vis[u]) continue; else return false; } else { vis[v] = -vis[u]; if (!dfs(v)) return false; } } return true;}bool solve(int u) { vis[u] = 1; for (int i = head[u]; ~i; i = edges[i].next) { int v = edges[i].to, w = match[v]; if (w < 0 || !vis[w] && solve(w)) { match[u] = v; match[v] = u; return true; } } return false;}int maxflow() { int ans = 0; memset(match, -1, sizeof(match)); for (int i = 1; i <= n; i++) { if (match[i] < 0) { memset(vis, 0, sizeof(vis)); if (solve(i)) ans++; } } return ans;}int main() { int u, v; while (~scanf("%d %d", &n, &m)) { init(); for (int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); addedge(u, v); addedge(v, u); } memset(vis, 0, sizeof(vis)); bool ok = true; for (int i = 1; i <= n; i++) { if (vis[i]) continue; vis[i] = 1; if (!dfs(i)) { ok = false; break; } } if (!ok) printf("No\n"); else printf("%d\n", maxflow()); }}

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