kruskal代码,30分求debug

P3366 【模板】最小生成树

yyyzrc123 @ 2023-10-08 17:11:28

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,tot,ans[100010],answer;
bool colour[10000010];
struct Node{int u,v,w;} e[100010];
bool cmp(Node a,Node b){return a.w<b.w;}
void add(int u,int v,int w){e[tot].u=u;e[tot].w=w;e[tot].v=v;tot++;}
void add2(int i){ans[cnt]=i;cnt++;}
//void print(int i){cout<<e[i].u<<' '<<e[i].v<<'\n';}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}
    sort(e,e+m,cmp);
    for(int i=0;i<m&&cnt<=n-1;i++){
        if(colour[e[i].u]&&colour[e[i].v])continue;
        add2(i);
        colour[e[i].u]=colour[e[i].v]=1;
    }
//  for(int i=0;i<cnt;i++)print(ans[i]);
    if(cnt<n-1){
        cout<<"orz";
        return 0;
    }
    for(int i=0;i<cnt;i++) answer+=e[i].w;
    cout<<answer;
    // cout<<"orz";
} 

by yyyzrc123 @ 2023-10-08 17:17:17


by BantM @ 2023-10-08 17:20:55

不能用染色啊,算法错误


by BantM @ 2023-10-08 17:22:29

好比说

1连2

3连4

那这时1234颜色都是1,那不就连不了边了吗?可是此时树不连通啊


by yyyzrc123 @ 2023-10-09 16:43:39

@Bant_Metor 谢谢,该问题已解决,使用并查集


by yyyzrc123 @ 2023-10-09 17:07:20

过了!!!


|