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

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

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

#include<iostream>              //prim  n^2

#include<cstdio>

#include<cstring>

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<n;i++)               //加入n-1条边

        {

          int minedge=inf; int vertex;     //每次找最小的边和新加入的点

            for(int j=1;j<=n;j++)

              if(mark[j]==0)

            {

                if(dis[j]>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<iostream>        //kruskal ,+并查集维护，m*logm

#include<vector>

#include<algorithm>

#include<cstdio>

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<b.w;

}

int main()

{

     int n;

    while(cin>>n&&n)

    {

        int m=n*(n-1)/2;

        vector<edge>v(m);

        for(int i=1;i<=n;i++)          //初始化并查集

           fa[i]=i;

       for(int i=0;i<m;i++)

       {

          scanf("%d%d",&v[i].x,&v[i].y);

          int temp;

          scanf("%d",&temp);

          v[i].w=temp;

        }

        int ans=0;

        sort(v.begin(),v.end(),my);    //排序

        for(int i=0,num=0;num<n-1;i++)      //取

        {

            int xx=father(v[i].x);int yy=father(v[i].y);

            if(xx!=yy)                  //不是同一个连通分量，合并之

            {

                ans+=v[i].w;

                fa[xx]=yy;

                num++;                      //发现一个有效边，共n-1条。

            }

        }

        printf("%d\n",ans);

    }

  return 0;

}

#include<iostream>                 //求无向图连通分支数，直接并查集。

#include<vector>

#include<algorithm>

#include<cstdio>

#include<set>

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<edge>v(m);

        for(int i=1;i<=n;i++)

         {

             fa[i]=i;                //初始化

         }

        for(int i=0;i<m;i++)

        {

          scanf("%d%d",&v[i].x,&v[i].y);

        }

        for(int i=0;i<m;i++)

        {

            int xx=father(v[i].x);     //x--y有边。

            int yy=father(v[i].y);

            fa[xx]=yy;

        }

        int count=0;

        set<int>se;

        for(int i=1;i<=n;i++)      //只需看有几个father（i）（等价类）,一个连通分量只对应一个。

        {

            se.insert(father(i));

        }

        count=se.size()-1;

        printf("%d\n",count);

    }

    return 0;

}

巴特西

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

最新文章

热门文章