Minimum Spanning Tree.prim/kruskal(并查集)-白红宇

Minimum Spanning Tree.prim/kruskal(并查集)

阅读量：6814 次

发布时间：2019-06-26

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

开始了最小生成树，以简单应用为例hoj1323,1232(求连通分支数，直接并查集即可)

prim（n*n）一般用于稠密图，而Kruskal（m*log(m)）用于系稀疏图

#include
    
                   //prim  n^2#include
     
      #include
      
       using namespace std;const int inf=0x3f3f3f3f;int a[102][102];int dis[102];int mark[102];int main(){    int n;    while(cin>>n&&n)    {        int m=n*(n-1)/2;        int x,y;        memset(a,0x3f,sizeof(a));        memset(dis,0x3f,sizeof(dis));        memset(mark,0,sizeof(mark));        while(m--)        {           scanf("%d%d",&x,&y);           int temp;           scanf("%d",&temp);           if(a[x][y]>temp)             a[x][y]=temp;          a[y][x]=a[x][y];        }        int ans=0;        int cur=1;        mark[cur]=1;        for(int i=1;i
       
        a[cur][j])      //更新                {                    dis[j]=a[cur][j];                }                if(minedge>dis[j])        //得最小边               {                 minedge=dis[j];                 vertex=j;               }             }             ans+=minedge;             cur=vertex;            //新加入的点cur             mark[cur]=1;          //已经加入        }        printf("%d\n",ans);    }    return 0;}

#include
    
             //kruskal ,+并查集维护，m*logm#include
     
      #include
      
       #include
       
        using namespace std;const int inf=0x3f3f3f3f;int fa[102];                 int father(int x){return (x==fa[x]?x:father(fa[x]));}struct edge                {    int x,y,w;};bool my(const edge &a,const edge &b)       //先按权重排序{    return a.w
        
         >n&&n)    {        int m=n*(n-1)/2;        vector
         
          v(m); for(int i=1;i<=n;i++) //初始化并查集 fa[i]=i; for(int i=0;i

#include
    
                      //求无向图连通分支数，直接并查集。#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int fa[1002];int father(int x){return (x==fa[x]?x:father(fa[x]));}struct edge{    int x,y;};int main(){    int n,m;    while(~scanf("%d",&n)&&n)    {        scanf("%d",&m);        vector
         
          v(m); for(int i=1;i<=n;i++) { fa[i]=i; //初始化 } for(int i=0;i