首页 > 代码库 > poj1679唯一最小生成树

poj1679唯一最小生成树

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;const int maxn=105;int father[maxn];int getfather(int x){    if(x!=father[x])        father[x]=getfather(father[x]);    return father[x];}struct Node{    int a;int b;int c;}node[maxn*maxn];int cmp(const Node &a,const Node &b){    return a.c<b.c;}int gg[maxn];int vis[maxn];int main(){    int Icase;int n,m;    while(cin>>Icase){        while(Icase--){            cin>>n>>m;            for(int i=1;i<=n;i++)father[i]=i;            for(int i=0;i<m;i++){                int a,b,c;cin>>a>>b>>c;                node[i].a=a;node[i].b=b;node[i].c=c;            }            sort(node,node+n,cmp);int ans=0;            int sum=0;            for(int i=0;i<m;i++){                int fa=getfather(node[i].a);int fb=getfather(node[i].b);int c=node[i].c;                if(fa!=fb){                    gg[ans++]=i;sum+=c;father[fa]=fb;                }            }            int ret=0;            memset(vis,0,sizeof(vis));            for(int i=0;i<ans;i++){                vis[gg[i]]=1; int ans1=0;int sum1=0;                for(int j=1;j<=n;j++) father[j]=j;                for(int j=0;j<m;j++){                    if(!vis[j]){                        int fa=getfather(node[j].a);int fb=getfather(node[j].b);int c=node[j].c;                        if(fa!=fb){                            sum1+=c;father[fa]=fb;                        }                    }                }                for(int j=1;j<=n;j++){                    if(father[j]==j) ans1++;                }             //   cout<<ans1<<" "<<sum1<<endl;system("pause");                if(ans1==1) if(sum1==sum) ret++;                vis[gg[i]]=0;            }            if(ret>0) cout<<"Not Unique!"<<endl;            else cout<<sum<<endl;        }    }    return 0;}