首页 > 代码库 > HDU 2444 The Accomodation of Students 二分图判定+最大匹配
HDU 2444 The Accomodation of Students 二分图判定+最大匹配
题目来源:HDU 2444 The Accomodation of Students
题意:n个人是否可以分成2组 每组的人不能相互认识 就是二分图判定 可以分成2组 每组选一个2个人认识可以去一个双人间 最多可以有几组
思路:二分图判定+最大匹配
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 550; int vis[maxn]; int y[maxn]; vector <int> G[maxn]; int n, m; int color[maxn]; bool bipartite(int u) { for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(color[u] == color[v]) return false; if(!color[v]) { color[v] = 3 - color[u]; if(!bipartite(v)) return false; } } return true; } bool dfs(int u) { for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(vis[v] || color[v] == 1) continue; vis[v] = true; if(y[v] == -1 || dfs(y[v])) { y[v] = u; return true; } } return false; } int match() { int ans = 0; memset(y, -1, sizeof(y)); for(int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); if(color[i] == 1 && dfs(i)) ans++; } return ans; } int main() { //int T; //scanf("%d", &T); while(scanf("%d %d", &n, &m) != EOF) { for(int i = 0; i <= n; i++) G[i].clear(); while(m--) { int u, v; scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } memset(color, 0, sizeof(color)); int flag = 0; for(int i = 1; i <= n; i++) if(!color[i]) { color[i] = 1; if(!bipartite(i)) { puts("No"); flag = 1; break; } } if(flag) continue; printf("%d\n", match()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。