prim和kruskal(最小生成树)(kruskal模板)

题目: P3366 【模板】最小生成树

n为点,m为边

prim:
    O(nlgn)    //以边遍历点,因其一边有两个点,所以每个点会有两次判断,所以复杂度为n^2,通过堆优化可以变成 nlgn
    prim是从一个点散出去找与其相连的未被访问的最小边
    所以要用前向星的add
kruskal:
    O(mlgm)    //复杂度主要是为边排序  //n小就用prim  //m小就用kruskal
    kruskal是从全局找未被访问的最小边
    所以只要边排序就够了,用不到add

前向星:没有add函数的node不是前向星
       通过前向星可以访问到与i相连点和边

以下是kruskal

#include<bits/stdc++.h>
using namespace std;
int const N=5e3+7;
int const M=2e5+7;
int n,m;
struct node{
    int a,next,len;
}e[M];
bool cmp(node a,node b){
    return a.len < b.len ;
}
int f[N];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
    f[find(x)]=find(y);
}
void kruskal(){
    int cnt=0,sum=0,flag=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1;i<=m;++i){
        int a=e[i].a , b=e[i].next ;
        if(find(a)!=find(b)){
            merge(a,b);
            cnt++;
            sum+=e[i].len ;
            if(cnt>=n-1) {
                flag=1;break;
            }
        }
    }
    if(flag) cout << sum;
    else cout << "orz";
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=m;++i){
        cin >> e[i].a >> e[i].next >> e[i].len ;
    }
    kruskal();       //克鲁斯卡尔 
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:39
在记录秋招的大魔王很...:别被忽悠了,我做了多年销售。我可以告诉你,这就是忽悠你的,销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的,谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪,你看那些跳槽去做经理主管的,底薪底一些,人家愿意去吗?所以那些说销售靠提成的纯属忽悠,除非他们的业务很容易成单。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
投递腾讯等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务