[模板]Kruskal && 并查集洛谷T3366、3367

【一年之后重新学习】系列第二弹。。。

Kruskal:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<cstdlib>
 7 
 8 #include<string>
 9 #include<stack>
10 #include<queue>
11 #include<vector>
12 #include<algorithm>
13 #include<map>
14 #include<set>
15 
16 using namespace std;
17 
18 inline void read(int &x){
19     x=0;
20     char t=getchar();
21     bool f=0;
22     
23     while(t<'0' || t>'9'){
24         if(t=='-')f=1;
25         t=getchar();
26     }
27     
28     while(t>='0' && t<='9'){
29         x=(x<<3)+(x<<1)+t-'0';
30         t=getchar();
31     }
32     
33     if(f)x=-x;
34 }
35 
36 void start();
37 int find(int);
38 
39 int pa[5010];
40 
41 int u[200010];
42 int v[200010];
43 int w[200010];
44 int first[5010];
45 int next[200010];
46 
47 int p[200010];
48 
49 bool cmp(int a,int b){
50     return w[a]<w[b];
51 }
52 
53 int n,m,i;
54 int js=0;
55 int x,y;
56 int ans=0;
57 
58 int main(){
59     start();
60     
61     read(n);read(m);
62     
63     for(i=1;i<=n;i++)pa[i]=i;
64     
65     for(i=1;i<=m;i++){
66         read(u[i]);read(v[i]);read(w[i]);
67         next[i]=first[u[i]];
68         first[u[i]]=i;
69         
70         p[i]=i;
71     }
72     
73     sort(p+1,p+1+m,cmp);
74     
75     for(i=1;i<=m && js<n-1;i++){
76         x=find(u[p[i]]);
77         y=find(v[p[i]]);
78         
79         if(x!=y){
80             js++;
81             ans+=w[p[i]];
82             pa[x]=y;
83         }
84     }
85     
86     if(js==n-1)printf("%d
",ans);else printf("orz
");
87     
88     return 0;
89 }
90 
91 void start(){
92     memset(first,0,sizeof(first));
93     memset(next,0,sizeof(next));
94 }
95 
96 int find(int x){
97     if(pa[x]==x)return x;
98     else return pa[x]=find(pa[x]);
99 }

并查集:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<cstdlib>
 7 
 8 #include<string>
 9 #include<stack>
10 #include<queue>
11 #include<vector>
12 #include<algorithm>
13 #include<map>
14 #include<set>
15 
16 using namespace std;
17 
18 inline void read(int &x){
19     x=0;
20     char t=getchar();
21     bool f=0;
22     
23     while(t<'0' || t>'9'){
24         if(t=='-')f=1;
25         t=getchar();
26     }
27     
28     while(t>='0' && t<='9'){
29         x=(x<<3)+(x<<1)+t-'0';
30         t=getchar();
31     }
32     
33     if(f)x=-x;
34 }
35 
36 int find(int);
37 
38 int pa[10010];
39 int n,m,i,f,a,b,x,y;
40 
41 int main(){
42     read(n);read(m);
43     
44     for(i=1;i<=n;i++)pa[i]=i;
45     for(i=1;i<=m;i++){
46         read(f);read(a);read(b);
47         x=find(a);y=find(b);
48         if(f==1)pa[x]=y;
49         else{
50             if(x==y)printf("Y
");
51             else printf("N
");
52         }
53     }
54     
55     return 0;
56 }
57 
58 int find(int x){
59     if(pa[x]==x)return x;
60     else return pa[x]=find(pa[x]);
61 }

[模板]Kruskal && 并查集 洛谷T3366、3367

[模板]Kruskal && 并查集洛谷T3366、3367