@[胖达和阿极](/user/90428) 双向边
by Qing_fy @ 2022-07-26 23:15:43
@[Qing_fy](/user/461366)
谢谢大佬
by 胖达和阿极 @ 2022-07-26 23:23:32
@[Qing_fy](/user/461366) ```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,m,fa[N];
struct edge{
int u,v,w;
bool operator <(const edge &a1) const{
return w<a1.w;
}
}a[N];
int find(int x){
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
bool cmp(edge a1,edge a2){
return a1.w<a2.w;
}
long long kruskal()
{
long long cnt = 0,sum =0;
sort(a+1,a+(m*2)+1,cmp);
for(int i=1;i<=m*2;i++){
if(find(a[i].u)!=find(a[i].v)){
fa[a[i].v] = fa[a[i].u];
sum += a[i].w;
cnt++;
if(cnt == n-1){
return sum;
}
}
}
return -1;
}
int main(){
cin>>n>>m;
int g1,g2,g3;
for(int i=1;i<=n;i++){
fa[i] = i;
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&g1,&g2,&g3);
a[i].u=g1;a[i].w=g3;a[i].v=g2;
a[i+m].u=g2;a[i+m].w=g3;a[i+m].v=g1;
}
int k1 = kruskal();
if(k1==-1){
cout<<"orz";
}else{
cout<<k1;
}
return 0;
}
```
大佬还是不太对
by 胖达和阿极 @ 2022-07-26 23:54:50
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,m,fa[N];
struct edge{
int u,v,w;
bool operator <(const edge &a1) const{
return w<a1.w;
}
}a[N];
int find(int x){
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
bool cmp(edge a1,edge a2){
return a1.w<a2.w;
}
long long kruskal()
{
long long cnt = 0,sum =0;
sort(a+1,a+(m*2)+1,cmp);
for(int i=1;i<=m*2;i++){
if(find(a[i].u)!=find(a[i].v)){
fa[a[i].v] = fa[a[i].u];
sum += a[i].w;
cnt++;
if(cnt == n-1){
return sum;
}
}
}
return -1;
}
int main(){
cin>>n>>m;
int g1,g2,g3;
for(int i=1;i<=n;i++){
fa[i] = i;
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&g1,&g2,&g3);
a[i].u=g1;a[i].w=g3;a[i].v=g2;
a[i+m].u=g2;a[i+m].w=g3;a[i+m].v=g1;
}
int k1 = kruskal();
if(k1==-1){
cout<<"orz";
}else{
cout<<k1;
}
return 0;
}
```
@[Qing_fy](/user/461366)
by 胖达和阿极 @ 2022-07-26 23:55:08
@[胖达和阿极](/user/90428) 用dfs判断图是否连通
by Waaifu_D @ 2022-07-27 07:17:43
```
if(find(a[i].u)!=find(a[i].v)){
fa[a[i].v] = fa[a[i].u];
```
改成
```cpp
if(find(a[i].u)!=find(a[i].v)){
fa[find(a[i].u)] = fa[find(a[i].v)];
by Waaifu_D @ 2022-07-27 07:19:30
并查集直接修改祖先的祖先就可以了
by Waaifu_D @ 2022-07-27 07:20:03
@[Waaifu_D](/user/358779) 可能不需要吧
by char_cha_ch @ 2022-07-27 11:40:13
@[Waaifu_D](/user/358779)
好，我晚上试一下，谢谢
by 胖达和阿极 @ 2022-07-27 20:48:13
其实有友元函数就可以用下优先队列了，个人认为有些时候优先队列一直都最棒的。
另外$\texttt{Kruskal}$算法本身就可以处理无向图，不必外加一条边，而且蓝书系列中的标程也没这么写，第二条语句就有点奇怪了(我真的没看懂在干嘛)。
by Benny_Li @ 2022-10-05 20:24:32