胖达和阿极 @ 2022-07-26 23:00:19

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+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+1,cmp);
    for(int i=1;i<=m;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;

    }
    int k1 = kruskal();
    if(k1==-1){
        cout<<"orz";
    }else{
        cout<<k1;
    }
    return 0;
}

by Qing_fy @ 2022-07-26 23:15:43

@胖达和阿极 双向边

by 胖达和阿极 @ 2022-07-26 23:23:32

@Qing_fy 谢谢大佬

by 胖达和阿极 @ 2022-07-26 23:54:50

@Qing_fy ```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+(m2)+1,cmp); for(int i=1;i<=m2;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:55:08

#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

by Waaifu_D @ 2022-07-27 07:17:43

@胖达和阿极 用dfs判断图是否连通

by Waaifu_D @ 2022-07-27 07:19:30

 if(find(a[i].u)!=find(a[i].v)){
            fa[a[i].v] = fa[a[i].u];

改成

 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:20:03

并查集直接修改祖先的祖先就可以了

by char_cha_ch @ 2022-07-27 11:40:13

@Waaifu_D 可能不需要吧

by 胖达和阿极 @ 2022-07-27 20:48:13

@Waaifu_D 好，我晚上试一下，谢谢

by Benny_Li @ 2022-10-05 20:24:32

其实有友元函数就可以用下优先队列了，个人认为有些时候优先队列一直都最棒的。

另外\texttt{Kruskal}算法本身就可以处理无向图，不必外加一条边，而且蓝书系列中的标程也没这么写，第二条语句就有点奇怪了(我真的没看懂在干嘛)。