首页 > 代码库 > HDU 2444 The Accomodation of Students(判断是否是二分图)
HDU 2444 The Accomodation of Students(判断是否是二分图)
题目链接
题意:n个学生,m对关系,每一对互相认识的能住一个房间。问否把这些学生分成两组,要求每组的学生都互不认识。求最多需要多少个房间。
是否能分成两组?也就是说判断是不是二分图,判断二分图的办法,用染色法
把初始点染成黑色,然后与之相连的染成白色,重复,使路径黑白相间,
如果当前点的颜色和与他相连点的颜色相同时,则说明这个图不是二分图
求最多需要多少个房间?也就是求最大匹配数。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <math.h> #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 310; const int maxm = 100001; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b const int N = 50010; int ma[maxn][maxn]; int line[maxn],color[maxn]; bool vis[maxn]; int k,n,m; bool flag; int DFS(int u) { for(int v = 1;v<=n;v++) { if(ma[u][v]==1 && !vis[v]) { vis[v] = 1; if(line[v]==-1 || DFS(line[v])) { line[v] = u; return 1; } } } return 0; } void dfs(int u,int st) { if(flag == false) return ; for(int v = 1;v <= n;v++) { if(ma[u][v]) { if(!color[v]) { color[v]= -st;//黑染白 / 白染黑 dfs(v,color[v]); } else if(color[v]==st) { flag = false; return; } } } } bool judge() { flag = true; color[1] = 1 ;//1代表黑色,-1代表白色 dfs(1,1) ; return flag; } int K_M() { int ans = 0; memset(line,-1,sizeof(line)); for(int i = 1;i<=n;i++) { init(vis); ans += DFS(i); } return ans; } int main() { int a,b; while(scanf("%d%d",&n,&m)!=EOF) { init(ma); memset(color,0,sizeof(color)); for(int i = 1;i<=m;i++) { scanf("%d%d",&a,&b); ma[a][b] = 1; } if(!judge()) { puts("No"); continue; } int ans = K_M(); printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。