Catalog
  1. 1. kruskal
    1. 1.0.1. 时间复杂度为O(nlogn)
    2. 1.0.2. 它的算法思路是这样的:
  • 2. prim
    1. 2.0.1. 时间复杂度O(n2)
  • 2.1. prim的堆优化
  • 最小生成树-学习

    隔了几个月,又开始写博客了qwq

    kruskal

    时间复杂度为O(nlogn)

    它的算法思路是这样的:

    我们根据边的权值将所有边排序,然后枚举每条边,用并查集去查询这条边的两个端点是否在同一集合内,若在同一集合内,则删掉这条边,若不在同一结合则加入这条边,并将这两个端点所在的集合合并。
    附一下代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>

    using namespace std;

    int n,m,q[6000];

    struct lalala{
    int x,y,z,save;
    }a[210000];

    int mysort(lalala a,lalala b)
    {
    return a.z < b.z;
    }

    int work(int x,int y)
    {
    while(q[q[x]] != q[x]) q[x] = q[q[x]];
    while(q[q[y]] != q[y]) q[y] = q[q[y]];
    if(q[x] == q[y]) return 1;
    else
    {
    q[q[y]] = q[x];
    return 0;
    }
    }

    int main()
    {
    long long ans = 0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) q[i]=i;
    for(int i=1; i<=m; i++)
    {
    cin>>a[i].x>>a[i].y>>a[i].z;
    ans += a[i].z;
    }
    sort(a+1,a+m+1,mysort);
    for(int i=1;i<=m;i++)
    {
    if(!work(a[i].x,a[i].y)) ans -= a[i].z;
    }
    cout << ans;
    return 0;
    }

    prim

    时间复杂度O(n2)

    跑得慢,代码长,没特殊功能,真不知道为什么要学它qwq……
    prim的思想和某最短路算法的思路是类似的,我们将更新过的点标为白色,没有更新过的标为蓝色,然后枚举每一个蓝点(按minn值从小到大更新,这里貌似可以用堆优化,然而我比较懒qwq)并更新为白点,并用它去更新其他的蓝点(这里不用把被更新的点标为白色,不然它们就没法更新其他点,也没法被其他的点更新了)。最后将每个点的minn值加起来就好啦。
    附一下代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #define ll long long
    #define INF 2147483647

    using namespace std;

    struct node{
    int k,dis;
    bool operator < ( const node &x )const{return x.dis < dis;}
    };

    priority_queue<node> que;

    long long n,m,s,d[1000005],cnt,D[1000005],v[1000005];

    struct Edge{
    int to,next,x;
    }edge[2000005];

    void add(int x,int y,int a)
    {
    edge[++cnt].to = y;
    edge[cnt].x = a;
    edge[cnt].next = d[x];
    d[x] = cnt;
    }

    int main()
    {
    int x,y,a;
    scanf("%lld%lld%lld",&n,&m,&s);
    for(register int i = 1; i <= m; i++)
    {
    scanf("%d%d%d",&x,&y,&a);
    add(x,y,a);
    }
    que.push((node){s,0});
    for(register int i = 1; i <= n; i++) D[i] = INF;
    D[s] = 0;
    while(!que.empty())
    {
    node u = que.top();
    que.pop();
    if(v[u.k]) continue;
    v[u.k] = 1;
    for(register int i = d[u.k]; i; i = edge[i].next)
    {
    if(D[edge[i].to] > D[u.k] + edge[i].x)
    {
    D[edge[i].to] = edge[i].x + D[u.k];
    if(!v[edge[i].to]) que.push((node){edge[i].to,D[edge[i].to]});
    }
    }
    }
    for(register int i = 1; i <= n; i++) printf("%d ",D[i]);
    printf("\n");
    return 0;
    }

    prim的堆优化

    既然prim和某最短路算法的思路是相似的,那么ta和某最短路算法一样也可以用堆优化,可以把时间复杂度从O(n2)降到O(nlongn)
    依然是跑得慢,代码长,没特殊功能qwq……
    附一下代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #define ll long long
    #define INF 0x7fffffff
    #define re register

    using namespace std;

    int read()
    {
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
    }

    struct edge{
    int x,y,z;
    }a[500005];

    struct EDGE{
    int next,to,x,save;
    }e[500005];

    struct node{
    int k,dis;
    bool operator < (const node & x) const {return x.dis < dis;}
    }now;

    priority_queue <node> que;

    int cnt,d[100005];

    void add(int x,int y,int a)
    {
    e[++cnt].to = y;
    e[cnt].x = a;
    e[cnt].next = d[x];
    d[x] = cnt;
    }

    int n,m,q,x,y,z,ans,minn[100005],vis[100005];

    int mysort(edge a1, edge a2)
    {
    if(a1.x != a2.x) return a1.x < a2.x;
    if(a1.y != a2.y) return a1.y < a2.y;
    return a1.z < a2.z;
    }

    int main()
    {
    n = read();
    m = read();
    for(re int i = 1; i <= m; i++)
    {
    a[i].x = read(); a[i].y = read(); a[i].z = read();
    }
    sort(a + 1, a + m + 1, mysort);
    for(re int i = 1; i <= m; i++)
    if(a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)
    {
    add(a[i].x, a[i].y, a[i].z);
    add(a[i].y, a[i].x, a[i].z);
    }
    for(re int i = 1; i <= n; i++) minn[i] = INF;
    que.push((node){1,0});
    while(!que.empty())
    {
    now = que.top();
    que.pop();
    vis[now.k] = 1;
    for(re int i = d[now.k]; i; i = e[i].next)
    if(!vis[e[i].to] && e[i].x < minn[e[i].to])
    {
    minn[e[i].to] = e[i].x;
    que.push((node){e[i].to,minn[e[i].to]});
    }
    }
    for(re int i = 2; i <= n; i++) ans = ans + minn[i];
    printf("%d\n",ans);
    return 0;
    }

    推荐例题:【模板】最小生成树

    Author: wflight
    Link: http://yoursite.com/2019/08/02/最小生成树-学习/
    Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
    Donate
    • 微信
    • 支付寶

    Comment