HDUOJ 1879继续畅通工程（并查集）-白红宇

HDUOJ 1879继续畅通工程（并查集）

阅读量：5356 次

发布时间：2019-06-15

本文共 2842 字，大约阅读时间需要 9 分钟。

1 #include 
     
       2 #include
      
        3 using namespace std; 4 struct home 5 { 6     int a; 7     int b; 8     int dis; 9     int _Construct;10 }v[5008];11 int father[200];12 int sum=0;13 int cmp(const void *a,const void *b)14 {15     struct home *c,*d;16     c=(struct home *)a;17     d=(struct home *)b;18     return c->dis-d->dis;19 }20 21 int findx(int x)22 {23     while(x!=father[x])24     x=father[x];25     return x;26 }27 void merge(home x)28 {29     int fx=findx(x.a),fy=findx(x.b);30     if(fx!=fy)31     {32         father[fx]=fy;33         if(x._Construct==0)34         sum+=x.dis;35     }36     37 }38 int main()39 {40     #ifdef inandout41        freopen("C:\\Users\\lx\\Desktop\\1.in","r",stdin);42     #endif43     44     int T;45     while(scanf("%d",&T),T!=0)46     {47         int i,j;48         int test=0;49         int n=T*(T-1)/2;50         for(i=1;i<=n;i++)51         scanf("%d%d%d%d",&v[i].a,&v[i].b,&v[i].dis,&v[i]._Construct);52         for(i=1;i<=T;i++)53         father[i]=i;54         qsort(v,n+1,sizeof(v[0]),cmp);55         for(i=1;i<=n;i++)56         {57             if(v[i]._Construct==1)58             merge(v[i]);59         }60         for(i=1;i<=n;i++)61         {62             merge(v[i]);63         }64         for(i=1;i<=T;i++)65         {66             if(i==father[i])67             test++;68         }69         if(test>1)70         printf("?\n");71         else72         printf("%d\n",sum);73         sum=0;74     }75         76     return 0;77 }

路径压缩版findx

int findx(int x){ if(x!=father[x])　　x=findx(father[x]); else 　　return x;}int findfast(int x){    if(x!=father[x])    　　father[x]=findx(father[x]);　　 else　　 　　return father[x];}

例HDU1181

#define DeBUG#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    using namespace std ;#define zero {0}#define INF 2000000000#define EPS 1e-6typedef long long LL;const double PI = acos(-1.0);inline int sgn(double x){ return fabs(x) < EPS ? 0 :(x < 0 ? -1 : 1);}int father[1000];int findx(int x){ if(x!=father[x])x=findx(father[x]); else return x;}int findfast(int x){ if(x!=father[x]) father[x]=findx(father[x]); else return father[x];}void merge(int a,int b){ int fx=findfast(a); int fy=findfast(b); if(fx!=fy) { father[fy]=fx; }}void init(){ for(int i=0;i<1000;i++) father[i]=i;}int main(){ #ifdef DeBUGs freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); #endif char s[1000]; int t=0; init(); while(scanf("%s", s)+1) { int len=strlen(s); merge(s[0],s[len-1]); if(s[0]=='0') { if(findx('m')=='b') printf("Yes.\n"); else printf("No.\n"); init(); } } return 0;}