HDU 2444 The Accomodation of Students——二分图判定+最大匹配

HDU 2444 The Accomodation of Students——二分图判定+最大匹配

判定后用匈牙利算法求出最大匹配

#include #include #include #include #include using namespace std;const int maxn = 500;int n, m;vector G[maxn];int vis[maxn];int s1[maxn], s2[maxn], n1, n2;bool used[maxn];int match[maxn];bool dfs(int u) { for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; 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 Edmons(int u) { for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(used[v]) continue; used[v] = true; if (match[v] == 0 || Edmons(match[v])) { match[v] = u; return true; } } return false;}int main() { while (~scanf("%d %d", &n, &m)) { int i; for (int i = 0; i <= n; i++) G[i].clear(); for (i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } memset(vis, 0, sizeof(vis)); for (i = 1; i <= n; i++) { if (vis[i]) continue; vis[i] = 1; if (!dfs(i)) break; } if (i <= n) printf("No\n"); else { n1 = n2 = 0; for (int i = 1; i <= n; i++) { if (vis[i] == 1) s1[++n1] = i; else if (vis[i] == -1) s2[++n2] = i; } for (int i = 1; i <= n; i++) match[i] = 0; int ans = 0; for (int i = 1; i <= n1; i++) { int u = s1[i]; memset(used, false, sizeof(used)); if (Edmons(u)) ans++; } printf("%d\n", ans); } } return 0;}

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