下面给大家介绍用Kruscal的简单变形就可以解决本题，时间复杂度为O(M+MlogM)，包括了快排的时间复杂度，0MS。
注意到Kruscal贪心每次找出边权最小的边判断能否合并，假设找到了一条边权最小的边，其两个顶点所在集合的根节点分别为x和y，
向后搜寻边权与当前边相同的边（即当前边权最小的边不唯一），若搜寻到的边两个顶点的根节点同样是x和y，则这两个集合合并就有了两种方法，
此时就可以直接输出NotUnique!并退出。这样除了qsort以外的时间复杂度就被控制在O(m)以内。

type
 rec=record u,v,w:longint; end;
var
 a:array[0..10000]of rec;
 fa:array[0..100]of longint;
 b:array[0..10000]of boolean;
 t,n,m,i,j,x,y,ans:longint;
 bool:boolean;
 
procedure qsort(l,r:longint);
 var
  i,j,x:longint;
  y:rec;
 begin
  i:=l; j:=r;
  x:=a[(l+r)>>1].w;
  repeat
   while a[i].w<x do inc(i);
   while x<a[j].w do dec(j);
   if not(i>j) then
    begin
     y:=a[i]; a[i]:=a[j]; a[j]:=y;
     inc(i); dec(j);
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
 end;
 
function find(x:longint):longint;
 begin
  if x=fa[x] then exit(x);
  fa[x]:=find(fa[x]);
  exit(fa[x]);
 end;
 
begin
 readln(t);
 repeat
  dec(t);
  readln(n,m);
  for i:=1 to m do with a[i] do read(u,v,w);
  qsort(1,m);
  fillchar(b,sizeof(b),0);
  for i:=1 to n do fa[i]:=i;
  bool:=false;
  ans:=0;
  i:=0;
  while i<m do
   begin
    inc(i);
    if b[i] then continue;
    x:=find(a[i].u);
    y:=find(a[i].v);
    if x=y then continue;
    for j:=i+1 to m do
     with a[j] do
      if not b[j] and(w=a[i].w)and(((find(u)=x)and(find(v)=y))or((find(u)=y)and(find(v)=x))) then
       begin bool:=true; b[j]:=true; end
      else break;
    if bool then break;
    fa[y]:=x;
    inc(ans,a[i].w);
   end;
  if bool then writeln('Not Unique!') else writeln(ans);
 until t=0;
end.

• Re:不用求次小生成树，直接用kruscal的简单变形，0ms (10) 201006021028 2011-11-06 13:04:42
• Re:不用求次小生成树，直接用kruscal的简单变形，0ms (17) sodawater 2011-11-09 16:23:22
• Re:不用求次小生成树，直接用kruscal的简单变形，0ms (72) sodawater 2011-11-10 16:19:15