程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 九度教程第75題

九度教程第75題

編輯:C++入門知識

C語言源碼: [cpp]   #include<stdio.h>   #include<stdlib.h>   #define maxsize 100   typedef struct edge   {       int a,b;       int weight;   }edge;   edge finished[maxsize*maxsize/2],notfinished[maxsize*maxsize/2];   int T[maxsize];   int findroot(int x)   {       int temp;       if(T[x]==-1)           return x;       else       {           temp=findroot(T[x]);           T[x]=temp;           return temp;       }   }   int cmp(const void *a,const void *b)   {       edge *aa=(edge *)a;       edge *bb=(edge *)b;       return aa->weight-bb->weight;   }   int main()   {       int n,a,b,c,d,topf,topn,min,i,roota,rootb;       scanf("%d",&n);       while(n)       {           topf=0;           topn=0;           for(i=1;i<=n*(n-1)/2;i++)           {               scanf("%d %d %d %d",&a,&b,&c,&d);               if(d==0)               {                   notfinished[topn].a=a-1;                   notfinished[topn].b=b-1;                   notfinished[topn++].weight=c;               }               else               {                   finished[topf].a=a-1;                   finished[topf].b=b-1;                   finished[topf++].weight=c;               }           }           for(i=0;i<n;i++)               T[i]=-1;           for(i=0;i<topf;i++)           {               roota=findroot(finished[i].a);               rootb=findroot(finished[i].b);               if(roota!=rootb)                   T[rootb]=roota;           }           min=0;   www.2cto.com         qsort(notfinished,topn,sizeof(notfinished[0]),cmp);           for(i=0;i<topn;i++)           {               roota=findroot(notfinished[i].a);               rootb=findroot(notfinished[i].b);               if(roota!=rootb)               {                   T[rootb]=roota;                   min+=notfinished[i].weight;               }           }           printf("%d\n",min);           scanf("%d",&n);       }   }  

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved