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

 1 #include <stdio.h>
 2 #include<iostream>
 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 inandout
41        freopen("C:\Users\lx\Desktop\1.in","r",stdin);
42     #endif
43     
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("?
");
71         else
72         printf("%d
",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 <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <set>
#include <sstream>
#include <map>
#include <bitset>
using namespace std ;
#define zero {0}
#define INF 2000000000
#define EPS 1e-6
typedef 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.
");
            else
                printf("No.
");
            init();
        }
    }
    
    return 0;
}

View Code