Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:水题 1A 附代码In Reply To:水题 1A 附代码 Posted by:bryant03 at 2015-02-14 15:25:25 > #include <cstdio> > #include <cstdlib> > #include <cstring> > #define N 101 > using namespace std; > int n,e,father[N]; > struct node { > int u,v,c; > node(){} > node(int u,int v,double c):u(u),v(v),c(c){} > }p[N*N]; > > void addnode(int u,int v,int c){ > p[e++]=node(u,v,c); > } > > int cmp(const void *a,const void * b){ > node *aa=(node *)a; > node *bb=(node *)b; > return aa->c - bb->c; > } > > int find(int x){ > if(x!=father[x]) > father[x]=find(father[x]); > return father[x]; > } > > void clear(){ > for(int i=0;i<=n;i++) > father[i]=i; > } > > int kruskal(int n){ > clear(); > int m=0, ans=0; > for(int i=0;i<e;i++){ > int u=find(p[i].u); > int v=find(p[i].v); > if(u==v) continue; > for(int j=i+1;j<e;j++){ > if(p[j].c!=p[i].c) break; > //printf("%d %d\n",) > if(find(p[j].u)==u&&find(p[j].v)==v){ > //printf("sdya"); > return -1; > } > } > m++; > ans+=p[i].c; > father[v]=u; > if(m==n-1) > break; > } > return ans; > } > > int main(){ > int t,l,a,b,c; > scanf("%d",&t); > while(t--){ > e=0; > scanf("%d%d",&n,&l); > for(int i=1;i<=l;i++){ > scanf("%d%d%d",&a,&b,&c); > if(a<b) addnode(a,b,c); > else addnode(b,a,c); > } > qsort(p,e,sizeof(p[1]),cmp); > int ans=kruskal(n); > if(ans==-1) printf("Not Unique!\n"); > else printf("%d\n",ans); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator