P3366 (模板)最小生成树

清疚 2021-09-29 03:18 313阅读 0赞

2019-01-30

**最小生成树基本算法**

**定义**：

给定一个边带权的无向图G=(V,E),n=|V|,m=|E|,由V中全部n个定点和E中n-1条边构成的无向连通子图被称为G的一颗生成树。

边的权值之和最小的生成树被称为无向图G的最小生成树。(Minimun Spanning Tree,MST).

**定理**：

任意一颗最小生成树一定包含无向图中权值最小的边

证明：

假设最小的边z不在MST上，将其加入树中，可构成一个环，并且环上所有边权都比z大，因此用z代表任意一条边，所得的生成树都一定会比原来更小。假设不成立。

**Kruskal：**  
桉边权排序，然后依次扫描每个边(x,y,z),若x，y属于同一个集合，则忽略这条边，否则合并x,y所在的集合，将z累加到答案中。---O(mlogm)

代码：

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    struct rec{
        int x,y,z;
    }e[200010];
    
    int cmp(rec a,rec b){
        return a.z<b.z;
    }
    int fa[5010],n,m,ans=0;
    
    int get(int x){
        if(x==fa[x])        return x;
        return fa[x]=get(fa[x]);
    }
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1 ; i<=m ; i++)
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
        sort(e+1,e+1+m,cmp);
        for(int i=1 ; i<=n ; i++)    fa[i]=i;
        
        for(int i=1 ; i<=m ; i++){
            int x=get(e[i].x);
            int y=get(e[i].y);
            if(x==y)    continue;
            fa[x]=y;
            ans+=e[i].z;
        }
        printf("%d\n",ans);    
        return 0; 
    }

**Prim**:

任一时刻，设已经确定属于最小生成树的节点集合为T,剩余点集合为S，找到minx€S,y€T 即两个端点分别属于S和T的权值最小的边，然后把点x从集合S中删除，加入集合T,并把该边边权累加到答案中。

具体来说，就是一个维护数组d\[x\]:  当x未被选中时，表示x与S中的节点间权值最小的边的权值。 若x已被选中，表示 x被选中加入已选集合时选中的最小边的权值。

遍历1~n-1每个点,每次选出T中d\[\]最小的点加入集合S，然后更新T中其它点的d值---O(n^2)，

代码：

Prim优先队列优化---O(mlogn)

const int N=3010;
    int a[N][N],d[N],n,m,ans;
    bool v[N];
    
    void prim()
    {
        memset(d,0x3f,sizeof(d));
        memset(v,0,sizeof(v));
        d[1]=0;
        for(int i=1 ; i<n ; i++)
        {
            int x(0);
            for(int j=1 ; j<=n ; j++)
                if(!v[j]&&d[j]<d[x]) x=j;
            v[x]=1;
            for(int y=1 ; y<=n ; y++)
                if(!v[y])
                    d[y]=min(d[y],d[x]+a[x][y]);
        }
    }
    
    int main()
    {
        prim();
        for(int i=2 ; i<=n ; i++)     ans+=d[i];
    }

转载于:https://www.cnblogs.com/wmq12138/p/10340197.html