首页 > 其他 > 详细

kruscal 模板

时间:2019-04-26 22:45:23      阅读:163      评论:0      收藏:0      [点我收藏+]
/*
   Kruskal模板 
*/
struct edge{
    int from;
    int to;
    int next;
    int value;
    bool operator<(const edge a) const{
         return value<a.value ;
    } 
};
const int inf=0x3f3f3f3f;
inline int find(int k){
    if(k==f[k]) return k;
    else return f[k]=find(f[k]);
}
inline int merge(int a,int b){
    if(find(a)!=find(b))
     return f[find(a)]=find(b);
}
inline void Kruskal(){
    sort(edge,edge+m);
    memset(dis,inf,sizeof(dis));
    for(int i=1;i<=m;i++){
        if(t==n-1) break;
        int u=edge[i].from ;
        int v=edge[i].to ;
        if(find(u)!=find(v)){
            merge(u,v);
            ans+=edge[i].value ;
            ++t;
        }
    }
} 

 

kruscal 模板

原文:https://www.cnblogs.com/nvwang123/p/10776794.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!