首先，我们分析一下分组的要求：
1、把所有的人分成2组，每组至少有1人；
2、每组之间的人两两认识。
    非常明显，如果存在两个人A和B，A不认识B，或B不认识A，那么A和B一定不能分在同一组。因此，我们以人为结点重新构造一个图G。假如A和B不能分在同一组，那么就在G中增加一条无向边(A,B)。这样，我们就得到了一个较为“单纯”的模型。下面我们对这个模型进行简单分析。
    我们先研究G的一个连通分量K1。对于这个连通分量，可以先求出K1的生成树T1。对于K1中的任意结点a，假如a在T1中的深度为奇数，我们就把a加入点集S1；否则我们把a加入点集S2（S1,S2最初为空集）。显然最后S1,S2的交集为空。
    不难证明，如果存在不同结点p和q，p和q同属于S1或S2，而且G中存在边(p,q)，那么要做到满足题目要求的分组是不可能的，应输出No solution。否则，我们就得到了连通分量K1的唯一分组方案：分为S1,S2两组。
    对于G中的每个连通分量Ki，我们可以求出相应的S1i,S2i。最后，我们的目的是把全部人分为2组。也就是说，对于i=1,2,3,...,m，我们必须决定把S1i中的人分到第1组，S2i中的人分到第2组，还是做刚好相反的处理。由于题目要求最后两组的总人数差最小，我们可以用动态规划的办法来确定究竟选取上面的哪种决策。
    不妨假设G中共有m个连通分量，记|S1i|=xi,|S2i|=yi(i=1,2,3,...,m)。我们用f[i,j]表示把前i个连同分量分为2组，且这两组总人数差的绝对值恰好为j是否可能。如果可能，f[i,j]=true；否则f[i,j]=false。初始条件是f[0,0]=true, f[0,x]=false(x=1,2,3,...)。然后我们可以按照如下方法确定f[i,j](0<i<=m, j>=0)：
    f[i,j]= f[i-1, j-Abs(xi-yi)] or f[i-1, j+Abs(xi-yi)];
    当然，在求解的同时，我们可以记录路径。最后，res=min{i: f[m, i]=true}即为最佳分组的人数差，而它对应的路径就是我们要求的分组方案。

有写出算法的希望能给我发邮件，共同讨论进步嘛嘿嘿。

• 好题 (999) lastone 2007-05-20 15:39:49
• Re:和大家一起讨论一下，这个题的确是够辣！！！ (8) ailyanlu 2007-05-21 10:55:37
• Re:和大家一起讨论一下，这个题的确是够辣！！！ (16) flatfish 2009-05-05 15:12:07