P3366 (模板)最小生成树

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
",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)，

代码：

#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
",ans);    
    return 0; 
}

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];
}