| ||||||||||
| 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