POJ 1679 The Unique MST(Kruskal+记录边)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#define maxn 105
using namespace std;
struct Node{
  int x,y,w;
  bool operator < (const Node &a) const{
    return a.w > w;
  }
}Edge[maxn * maxn];
int pre[maxn],cnt[maxn],num;
int T,n,m,ans;
bool flag;

void init(){
  for(int i=0;i<=n;i++) pre[i] = i;
}

void add(int u,int v,int w){
  Edge[num].x = u;
  Edge[num].y = v;
  Edge[num++].w = w;
}

int Find(int x){
  if(x != pre[x]) pre[x] = Find(pre[x]);
  return pre[x];
}

void Kruskal(){
  ans = 0;
  int xx = 0;
  sort(Edge, Edge + num);
  for(int i=0;i<m;i++){
    int fx = Find(Edge[i].x);
    int fy = Find(Edge[i].y);
    if(fx != fy){
      pre[fy] = fx;
      cnt[xx++] = i;
      ans += Edge[i].w;
    }
  }
  for(int k=0;k<xx;k++){
    init();
    int sum = 0;
    int yy = 0;
    for(int i=0;i<m;i++){
      if(i == cnt[k]) continue;
      int fx = Find(Edge[i].x);
      int fy = Find(Edge[i].y);
      if(fx != fy){
        pre[fy] = fx;
        yy ++;
        sum += Edge[i].w;
      }
    }
    if(yy == n - 1 && sum == ans){
      flag = false;
      return ;
    }
  }
}

int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++){
      int u, v, w;
      scanf("%d%d%d",&u,&v,&w);
      add(u, v, w);
      // add(v, u, w);
    }
    num = 0;
    flag = true;
    Kruskal();
    if(flag) printf("%d\n", ans);
    else puts("Not Unique!");
  }
  return 0;
}