UC知道pascal题解——幼儿园分组
来源：百度知道 编辑：UC知道 时间：2024/05/02 12:42:23
问题描述：
幼儿园里有n个小孩。不幸的是小孩常常打架。每个小孩有不超过3个仇敌。是否有可能将所有小孩分成两组使得每个小孩最多和它的一个仇敌同组？
输入文件（TEAM.IN）：
输入文件的第一行包含整数n <= 7163，接下来n行描述了每个小孩的仇敌，形式如同：
sum，A1,A2…Asum。
输出文件（TEAM.OUT）：
输出文件的第一行是人数较少的那一组的小孩数目（可以是0），接下来一行给出了该组小孩的清单。如果两组人数相同，你必须输出包含小孩1的那一组。如果存在多组解，任意一组即可；如果无解，输出'NO SOLUTION'。
输入输出样例：
TEAM.IN
8
3 2 3 7-
3 1 3 7
3 1 2 7
1 6
0
2 4 8
3 1 2 3
1 6
TEAM.OUT
4
1 2 5 6
本人用的是FREE PASCAL，不必考虑溢出问题
幼儿园里有n个小孩。不幸的是小孩常常打架。每个小孩有不超过3个仇敌。是否有可能将所有小孩分成两组使得每个小孩最多和它的一个仇敌同组？
输入文件（TEAM.IN）：
输入文件的第一行包含整数n <= 7163，接下来n行描述了每个小孩的仇敌，形式如同：
sum，A1,A2…Asum。
输出文件（TEAM.OUT）：
输出文件的第一行是人数较少的那一组的小孩数目（可以是0），接下来一行给出了该组小孩的清单。如果两组人数相同，你必须输出包含小孩1的那一组。如果存在多组解，任意一组即可；如果无解，输出'NO SOLUTION'。
输入输出样例：
TEAM.IN
8
3 2 3 7-
3 1 3 7
3 1 2 7
1 6
0
2 4 8
3 1 2 3
1 6
TEAM.OUT
4
1 2 5 6
本人用的是FREE PASCAL，不必考虑溢出问题
样例是什么意思啊？A表示什么，sum又表示什么。
我的感觉是用图来做，构造一个有向图，然后将它划分成两个子图，使每一个节点的初度<=1.当然搜索+剪枝也能过一部分点的