如何判断orz

P3366 【模板】最小生成树

chenzhiyuan0923 @ 2022-10-16 20:22:48

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int maxv=2e5+10;
long long n,m,f[maxv];
long long ans;
struct edge{
    int u,v,w;
};
edge g[maxn];
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int find(int a){
    if(f[a]==a) return a;
    f[a]=find(f[a]);
    return f[a];
}
void kruskal(){
    int cnt=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) {
        int x=g[i].u,y=g[i].v;
        int fx=find(x);
        int fy=find(y);
        if(fy!=fx){
            f[fx]=fy;
            ans+=g[i].w;
            cnt++;
        }
        if(cnt==n-1) break; 
    } 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) 
        scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
    sort(g+1,g+1+m,cmp);
    kruskal();
    cout<<ans;
}

by ImposterAnYu @ 2022-10-16 20:25:24

@xchenzhiyuan 是不是就是,如果所有的 m 条边都判完之后还没能挑 n = 1 条边,就代表图不连通


by ImposterAnYu @ 2022-10-16 20:26:08

@owo_ImposterAnYu_owo 打错了,是

如果所有的 m 条边都判完之后还没能挑出 n - 1 条边,就代表图不连通


by Im3tsmh @ 2022-10-16 20:30:32

@Yanyu_Kruay 你这个只能判定 1n 连了啊


by Im3tsmh @ 2022-10-16 20:31:46

在每次连边的时候记录 cntcnt=n-1 就连通了


by Yiowerr @ 2022-10-16 20:33:35

@TryToThink 当时写的时候没注意dbq ww


by chenzhiyuan0923 @ 2022-10-16 20:56:38

@owo_ImposterAnYu_owo 感谢,已A


by chenzhiyuan0923 @ 2022-10-16 20:57:05

@TryToThink 感谢


|