http://poj.org/problem?id=1679

#include<cstdio>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;
const int N=10000+10;
int father[N+N];
int grade[N+N];
int component;
struct Edge
{
    int from,to,w;
    bool operator <(const Edge& that) const
    {
        return w<that.w;
    }
}arr[50010],tmp;
int parent(int v)
{
    while(v!=father[v])
    {
        father[v]=father[father[v]];
        v=father[v];
    }
    return v;
}
int connect(int a,int b)
{
    int fa=parent(a);
    int fb=parent(b);
    if(fa==fb) return 0;
    if(grade[fa]>grade[fb])
    {
        father[fb]=fa;
        grade[fa]+=grade[fb];
    }
    else
    {
        father[fa]=fb;
        grade[fb]+=grade[fa];
    }
    component--;
    return 1;

}
int main()
{
    int t,n,m,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        component=n;
        vector<int> edge;
        for(int i=1;i<=n;i++)
        {
            father[i]=i;
            grade[i]=1;
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&arr[i].from,&arr[i].to,&arr[i].w);
        }
        sort(arr,arr+m);
        int ans=0;
        for(int i=0;i<m;i++)
        {
            int a=arr[i].from,b=arr[i].to;
            if(connect(a,b))
            {
                ans+=arr[i].w;
                edge.push_back(i);
            }
        }
        if(component!=1)
        {
            printf("Not Unique!\n");
        }
        bool flag=false;
        for(vector<int>::iterator it=edge.begin();it!=edge.end();it++)
        {
            for(int i=1;i<=n;i++)
            {
                father[i]=i;
                grade[i]=1;
            }
            component=n;
            int sum=0;
            for(int i=0;i<m;i++)
            {
                int a=arr[i].from,b=arr[i].to;
                if((i!=(*it))&&connect(a,b))
                {
                    sum+=arr[i].w;
                   // printf("a:%d b:%d\n",a,b);
                }
            }
           // printf("sum:%d\n",sum);
            if(component!=1) continue;
            if(sum==ans)
            {
                flag=true;
                break;
            }
        }
        if(flag) printf("Not Unique!\n");
        else printf("%d\n",ans);
    }

}