kruskal算法最后一个点不对，怎么办

mopeicong @ 2024-08-16 10:12:41

#include<bits/stdc++.h>
using namespace std;
int parent[1000010],n,cnt,m;

struct node{
    int from,to;
    int weight;
}edge[1000010];

void add(int i,int j,int w){
    cnt++;
    edge[cnt].from = i;
    edge[cnt].to = j;
    edge[cnt].weight = w;
}

bool cmp(node x,node y){
    return x.weight < y.weight;
}

int findroot(int x){
    if(parent[x]!=x){
        parent[x]=findroot(parent[x]);
    }
    return parent[x];
}

int main(){
    int u,v,w,ans=0,c=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) parent[i]=i;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    sort(edge+1,edge+1+cnt,cmp);
    for(int i=1;i<=cnt;i++){
        int u=edge[i].from;
        int v=edge[i].to;
        if(findroot(u)==findroot(v)) continue;
        parent[findroot(u)] = findroot(v);
        ans += edge[i].weight;
        c++;
        if(c==n-1){
            break;
        }
    }
    cout<<ans;
    return 0;
}

by Rigel @ 2024-08-16 10:17:34

审题，如果该图不连通则输出 orz

by mopeicong @ 2024-08-16 10:20:18

没看到，谢谢

by mopeicong @ 2024-08-16 10:22:03

又交了一遍，还是不对

#include<bits/stdc++.h>
using namespace std;
int parent[1000010],n,cnt,m;

struct node{
    int from,to;
    int weight;
}edge[1000010];

void add(int i,int j,int w){
    cnt++;
    edge[cnt].from = i;
    edge[cnt].to = j;
    edge[cnt].weight = w;
}

bool cmp(node x,node y){
    return x.weight < y.weight;
}

int findroot(int x){
    if(parent[x]!=x){
        parent[x]=findroot(parent[x]);
    }
    return parent[x];
}

int main(){
    int u,v,w,ans=0,c=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) parent[i]=i;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    sort(edge+1,edge+1+cnt,cmp);
    for(int i=1;i<=cnt;i++){
        int u=edge[i].from;
        int v=edge[i].to;
        if(findroot(u)==findroot(v)) continue;
        parent[findroot(u)] = findroot(v);
        ans += edge[i].weight;
        c++;
        if(c==n-1){
            break;
        }
    }
    if(ans!=0) cout<<ans;
    else cout<<"orz";
    return 0;
}

后面已经加了判断了

by apzzzx @ 2024-08-16 10:24:06

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50,M=5e5+50;
int n,m,ans;
int p[N],sz[N];
struct Edge{
    int u,v,w; 
}e[M];
bool cmp(Edge x,Edge y){
    return x.w<y.w;
}
int get_p(int x){
    return p[x]==x?x:p[x]=get_p(p[x]);
}
void Kruskal(){
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;i++) p[i]=i,sz[i]=1; 
for(int i=1;i<=m;i++){
    int x=get_p(e[i].u);
    int y=get_p(e[i].v);
    if(x==y) continue;
    p[x]=y; ans+=e[i].w;
    sz[y]+=sz[x];
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i)
        cin>>e[i].u>>e[i].v>>e[i].w;
        Kruskal();
    if(sz[get_p(1)]!=n) cout<<"orz"<<endl;
    else cout<<ans<<endl;

    return 0;
}

本蒟蒻只能帮到这了

@mopeicong

by Rigel @ 2024-08-16 10:25:23

不连通 ans 就一定等于 0 ？ 自己思考。

by Melo_DDD @ 2024-08-16 10:26:48

@mopeicong 你判断的不对

by mopeicong @ 2024-08-16 10:36:39

谢谢大家，通过了