最小生成树板子-白红宇

最小生成树板子

阅读量：6416 次

发布时间：2019-06-23

本文共 1455 字，大约阅读时间需要 4 分钟。

kruskal算法：

#include
     
      #include
      
       #include
       
        using namespace std;struct Node{    int a,b,val;    friend bool operator < (const Node& x,const Node& y){        return x.val< y.val;  //对于sort重载的话，从小到大用小于号    }}load[1000];int sum=0;int n,m;int fa[1000];int cnt=0;int Find(int a){    return fa[a]==a ? a : fa[a]=Find(fa[a]);}void init(int a,int b){    fa[Find(b)]=Find(a);}void kruskal(){    for(int i=0;i
        
         >n>>m;    for(int i=0;i
         
          >load[i].a>>load[i].b>>load[i].val;    }    for(int i=1;i<=n;i++){        fa[i]=i;    }    sort(load,load+m);    kruskal();    cout<
          
           <

prim算法

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;struct Node{ int d,len; friend bool operator < (const Node& a,const Node& b){ return a.len > b.len; //对于优先队列，从小到大排序用大于号 }};int n,m;int cnt,sum;int vis[1000];vector < Node > v[1000];priority_queue< Node > q;void prim(){ vis[1]=1; for(int i=0;i
             
              >m>>n){ if(m==0) break; cnt=sum=0; while(!q.empty()){ q.pop(); } for(int i=0;i<=n;i++){ v[i].clear(); } memset(vis,0,sizeof(vis)); for(int i=0;i
              
               >x>>y>>z; Node tmp; tmp.d=y; tmp.len=z; v[x].push_back(tmp); tmp.d=x; v[y].push_back(tmp); } prim(); if(cnt==n-1){ cout<
               
                <