题目链接：
题目描述：
n个小朋友要被分成两班，但是有些小朋友之间是不认得的，所以规定不能把不认识的小朋友分在一个班级里面，并且一班的人数要比二班的人数多，每个班的人数都大于零。
解题思路：
hdu给出的题解是二分图匹配加上贪心，就不多说了。
还可以用bfs对节点染色，建好图后，对节点进行bfs分成，偶数成与奇数成染成不同的颜色，颜色相同的节点都可以分到同一个集合里面，但是要判断一下奇环，如果出现奇环的话，是无法进行分组的。在每次bfs的时候再加上贪心累计求和。
1 #include <queue> 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 using namespace std; 8 const int maxn = 100010; 9 vector < int > G[maxn]; 10 11 int x, y, n, m, vis[maxn], flag; 12 void bfs (int s) 13 { 14 int p, q, zreo, one, num; 15 queue <int> Q; 16 zreo = 1; 17 one = vis[s] = 0; 18 Q.push(s); 19 while (!Q.empty()) 20 { 21 p = Q.front(); 22 Q.pop(); 23 num = (vis[p] + 1) % 2; 24 for (int i=0; i<G[p].size(); i++) 25 { 26 q = G[p][i]; 27 if (vis[q]!=-1 && num != vis[q]) 28 flag = 1; 29 if (vis[q]==-1) 30 { 31 Q.push(q); 32 vis[q] = num; 33 if (num == 0) 34 zreo ++; 35 else 36 one ++; 37 } 38 } 39 } 40 x += max (zreo, one); 41 y += min (one, zreo); 42 } 43 int main () 44 { 45 int t; 46 scanf ("%d", &t); 47 while (t --) 48 { 49 scanf ("%d %d", &n, &m); 50 memset (vis, -1, sizeof(vis)); 51 for (int i=0; i<=n; i++) 52 G[i].clear(); 53 x = y = flag = 0; 54 while (m --) 55 { 56 int a, b; 57 scanf ("%d %d", &a, &b); 58 G[a].push_back (b); 59 G[b].push_back (a); 60 } 61 for (int i=1; i<=n; i++) 62 { 63 if (vis[i] == -1) 64 bfs (i); 65 if (flag) 66 break; 67 } 68 if (x == n) 69 { 70 x --; 71 y ++; 72 } 73 if (flag || x < 1 || y < 1) 74 printf ("Poor wyh "); 75 else 76 printf ("%d %d ", x, y); 77 } 78 return 0; 79 }
用二分图匹配要比bfs快一半，内存也要少好多，所以再贴一个二分图匹配的代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 const int maxn = 100010; 7 struct Edge 8 { 9 int to, next; 10 }edge[2*maxn]; 11 int tot, head[maxn], vis[maxn]; 12 13 void init () 14 { 15 tot = 0; 16 memset (head, -1, sizeof(head)); 17 } 18 void Add (int from, int to) 19 { 20 edge[tot].to = to; 21 edge[tot].next = head[from]; 22 head[from] = tot ++; 23 } 24 bool dfs (int x, int c, int &a, int &b) 25 { 26 b ++; 27 if (c) 28 a ++; 29 vis[x] = c; 30 for (int i=head[x]; i!=-1; i=edge[i].next) 31 { 32 int num = edge[i].to; 33 if (vis[num] == c) 34 return false; 35 if (vis[num] == -1 && !dfs(num, c^1, a, b)) 36 return false; 37 } 38 return true; 39 } 40 int main () 41 { 42 int t, n, m; 43 scanf ("%d", &t); 44 while (t --) 45 { 46 scanf ("%d %d", &n, &m); 47 init (); 48 while (m --) 49 { 50 int a, b; 51 scanf ("%d %d", &a, &b); 52 Add (a, b); 53 Add (b, a); 54 } 55 int x, y; 56 bool flag = true; 57 memset (vis, -1, sizeof(vis)); 58 x = y = 0; 59 for (int i=1; i<=n; i++) 60 { 61 int a, b; 62 a = b = 0; 63 if (vis[i] == -1) 64 { 65 if (!dfs (i, 0, a, b)) 66 { 67 flag = false; 68 break; 69 } 70 } 71 x += max (a, b - a); 72 y += min (a, b - a); 73 } 74 if (x == n) 75 { 76 x --; 77 y ++; 78 } 79 if (!flag || x<1 || y<1) 80 printf ("Poor wyh "); 81 else 82 printf ("%d %d ", x, y); 83 } 84 return 0; 85 }