题目链接:
题目大意:
有编号为1~n的n个人,给出每个人认识的人的编号,注意A认识B,B不一定认识A,让你将所有的人分成两组,要求每组的人相互认识,且两组的人数要尽可能的接近。
求出每组的人的编号。
解题思路:
图论+背包(输出物品)。
相互认识的关系不好确定分组,如果转换思路,考虑相互不认识的情况就简单好多,如果A不认识B,且B不认识C,那么A和C必须分到同一组里。所以就想到了,连通分量的染色,相邻的两个染不同的颜色(0或1),每一个连通分量分成两组,并且相同颜色的人不能有边(一定要相互认识),容易知道不同连通分量的人一定相互认识,否则是连通的。
然后问题就转化为有多个连通分量,每个连通分量有两组,每组必须属于一个队,求两个队的人数差最小,并分别输出两队的人。
dp[i][j]表示到了第i个连通分量,且第一个队的人数为j时是否能够恰好凑齐。
ans[i][j]表示对应于状态dp[i][j]时的选择,0表示选择0颜色的节点,1表示选择1颜色的节点。
求出dp[num][]后,根据ans[num][]的值往前推,颜色选好后把所有的该颜色节点都加进去该队里去。
代码:
#include #include #include #include #include #include #include #include #include