Problem Description
唉, 小朋友是比较麻烦的。在一个幼儿园里,老师要上一节游戏课,有N个小朋友要玩游戏,做游戏时要用小皮球,但是幼儿园里只有M个小皮球,而且有些小朋友不喜 欢和一些小朋友在一起玩,而只喜欢和另一些小朋友一起玩,比如傻妞只喜欢和傻瓜,傻根,傻蛋们一起玩,傻根又不喜欢和傻蛋一起玩,傻蛋喜欢和傻子一起玩。 所以老师只好把他们分组,每个组至少有一个小球可以玩,而且每个组内不会有两个小朋友,相互不喜欢。现在给你这样一个幼儿园里小朋友之间关系的描述,做为 老师,是否可以上好这节游戏课。
Input
数 据有多个case,每个case先输入两个值N(1<=N<=10)和M(1<=M<=10),表示有N个小朋友(从0到N-1 标号),和M个小皮球。接着有N行,第i行先输入一个K(0<=K<N),表示第i个小朋友有喜欢一起玩的其他小朋友的个数,然后后面有K个 整数,表示K个小朋友的标号(不重复)。如果A喜欢和B一起玩,则B也喜欢和A一起玩,这个数据在输入时保证。两个case之间有空行
Output
对于每个case,如果老师可以上好课,输出YES,否则NO。
Sample Input
3 2 2 1 2 2 2 0 2 0 1
Sample Output
YES
参考思路:http://www.cnblogs.com/jackge/p/3228479.html
代码:
#include <iostream> #include <string.h> int root[15]; int map[15][15]; int children = 0, balls = 0; bool isOK = false; bool dfs(int x, int y) // x代表人数(编号:第x个人),y代表用掉的球数 { if (y > balls) // 用掉的球数已经超出预算 { return false; } if (x == children) { return true; } for (int i = 0; i < x; i++) { if (root[i] != i) // 一个集合用一个根来表示 { continue; } bool flag = true; for (int j = 0; j < x; j++) { if (root[j] == i) { if (map[x][j] != 1) { flag = false; break; } } } if (flag) { root[x] = i; if (dfs(x + 1, y)) // 归入已有集合 { return true; } root[x] = x; } } return dfs(x + 1, y + 1); // 分配新集合,已经用掉1个球,数目增加1 } int main() { while (scanf("%d%d", &children, &balls) != EOF) { memset(map, 0, sizeof(map)); for (int i = 0; i < children; i++) { root[i] = i; } for (int i = 0; i < children; i++) { int cnt; scanf("%d", &cnt); for (int j = 0; j < cnt; j++) { int t; scanf("%d", &t); map[i][t] = map[t][i] = 1; } } if (balls >= children) { printf("YES\n"); } else { if (dfs(0, 0)) { printf("YES\n"); } else { printf("NO\n"); } } } system("pause"); return 0; }
原文:http://my.oschina.net/keyven/blog/500432