本题N高达60，用暴搜肯定不行。
我这里有几个威力很弱的剪枝：
（1）如果对于两个集合A、B，A是B的子集，则A就可以删掉。如果A=B，则在A、B中任意删掉一个。
（2）如果某个整数只在一个集合里出现了，则这个集合必选（如样例中的集合2），在搜索时也可以删掉它。
（3）先选A再选B和先选B再选A效果一样，所以规定后面选的集合必须在前面的位置之后，如不能先选集合2再选集合1。
（4）可以从小到大枚举选的集合数（范围是N DIV K到N），若选X个集合时找到了解，则X就是结果。

可是……这几个剪枝还无法保证在最坏情况下不超时……请问大家有没有更好的剪枝？

试一下不枚举集合，枚举数字：
剪枝：
 统计每个数字在每个集合中出现的次数，从出现次数最小的数开始枚举

怎么枚举？请说一下。

分析：F[I，J]表示I至J取得的最优化合并，它有D[I，J]种状态，分别用L[I，J，K]表示，因此状态转移

F[I，J]：=MIN{F[I，K]+F[K+1，J]}


你看看这个动态规划怎么样
program  kmn;
   type ty=set of 1..60;
  var d,f:array[1..60,1..60]of integer;
      l:array[1..60,1..60,1..60]of ty;
      w,s,i1,j1,i,j,k,m,n,x:integer;
  function ttt(var a,b:ty):integer;
     var i,t:integer;
     begin
        i:=0;
        for t:=1 to m do
          if (t in a)and(t in b) then i:=i+1;
          exit(i);
        end;
      begin
      readln(n,m);
      fillchar(d,sizeof(d),0);
      fillchar(f,sizeof(f),0);
      fillchar(l,sizeof(l),0);
      for i:=1 to n do
         begin
           read(k);
           for j:=1 to k do
              begin
                 read(x);
                 f[x,x]:=1;inc(d[x,x]);l[x,x,d[x,x]]:=[i];
                 end;
                 readln;
         end;
     for k:=1 to m-1 do
        for i:=1 to m-k do
          for j:=1 to k do
            begin
                s:=maxint;
                for i1:=1 to d[i,i+j-1] do
                   for j1:=1 to d[i+j,i+k] do
                      begin
                         w:=f[i,i+j-1]+f[i+j,i+k];
                         w:=w-ttt(l[i,i+j-1,i1],l[i+j,i+k,j1]);
                         if w<s then begin
                                        x:=1;l[i,j,x]:=l[i,i+j-1,i1]+l[i+j,i+k,j1];
                                       s:=w;
                                       end
                   else if w=s then begin
                                       inc(x);l[i,j,x]:=l[i,i+j-1,i1]+l[i+j,i+k,j1];
                                       end;
                        end;
                        f[i,i+k]:=s;d[i,i+k]:=x;
              end;
        writeln(f[1,m]);
end.

如果全选然后往下删除...

4楼太棒了，时间复杂度O(n^3)的，比搜索好多了。

谢谢你解决了这道超难的题！