首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。