poj 1112 Team Them Up!

这道题得纪念一下，花了挺多时间的，做完回头看也不太难的，就是比较麻烦，要比较仔细。

题目大意是：有一群人，他们之间有些人互不认识，要将他们分组，使得每个组中的所有人都互相认识，并且两个组的人数之差最小，可能不存在分组满足要求条件。

很显然是一个图论的题目，将人考虑成点，不认识的人之间加一条边，则可以得到若干个连通图，对每个连通图作广度优先搜索，将互不认识的人分在不同的小组，如果此过程发现不满足要求的情况直接退出，否则就可以将所有人分成若干块，每块中有两组人员。用程序语言就是：

    S = {{X1, Y1}, {X2, Y2}, ..., {Xn, Yn}}, 将所有X和Y分成两组，满足Xi与Yi在不同的组，且两组的数量和之差最小。

这个可以用动态规划求解：

    dp(i, x) 表示第i组，第一组的数量为x时的两组数量和之差，则有递推方程：

    dp(i, x) = min (dp(i-1, x-Xi), dp(i-1, x-Yi))

因为Xi和Yi中任何一个都可以被分到第一组。

在动态规划的过程中，记录每次X和Y的分组情况即可。