精华内容
下载资源
问答
  • 最小生成树: 所有生成树中和最小生成树 比如下面图1的最小生成树是图2 图1 图2时间复杂度O(ElogE)E是边数代码实现#include #include using namespace std;const int N = 1e5 +

    算法作用

    计算最小生成树
    生成树: 将一个图的顶点不变, 通过去除一些边, 使它成为一棵树
    最小生成树: 所有生成树中的边权和最小的生成树
    比如下面图1的最小生成树是图2
    这里写图片描述
    图1
    这里写图片描述
    图2

    时间复杂度

    O(ElogE)E是边数

    代码实现

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N = 1e5 + 10;
    const int M = 1e5 + 10;
    int pa[N];
    
    struct Edge {
        int from, to, cost;
        bool operator < (const Edge & rhs) const {
            return cost < rhs.cost;
        }
    };
    
    Edge oldEdge[N], newEdge[N];
    
    int find(int x) {
        return x == pa[x] ? x : pa[x] = find(pa[x]);
    }
    
    void readData();
    
    int main() {
        readDate();
        for(int i = 0; i < n; ++i)
            pa[i] = i;
        int cnt = 0;
        sort(oldEdge, olEdge + m);
        for(int i = 0; i < m; ++i) {
            int fx = find(oldEdge[i].from);
            int fy = find(oldEdge[i].to);
            if(fx == fy) continue;
            pa[fx] = fy;
            newEdge[cnt++] = oldEdge[i];
        }
    }

    其中oldEdge是老图, newEdge是新图, n是顶点数, m是边数, pa是用来实现并查集的父亲指向
    代码的主体部分仅两个
    1. sort的排序函数
    2. find的并查集查找函数(包括后面的合并操作)
    其中以前的图以边的方式存储在oldEdge中, 得到的新图的边同样以边的方式存在newEdge中, 如果想用邻接矩阵, 邻接表或者链式前向星等, 转化一下即可

    算法拓展

    某些看似和路径无关的可以转移过来, 看个人灵活性了吧

    算法证明

    算法的基本思想是: 从最小的边开始, 一直找, 不停的合并到新图中, 直到遍历所有边
    证明: 反证法
    设由Kruskal算法生成的T0序列为e1, e2, e3 … ev-1,假设其不是最小生成树。任意最小生成树T定义函数f(T):T0中不存在于T中边在T0的下标。设T1是使f(T)最大的变量,设f(T1)=k,即ek不存在于T1中,T1为树且ek不在T1中,所以由引理1得T1+ek必存在圈C,C上必有e,k ≠ek,e,k不在T0 中。现令T2 = T1 - e,k + ek,则T2也为生成树但由Kruskal算法可知ek是使e1, e2 … ek-1, ek无圈的权值最小的边,e1, e2 … ek-1, e,k是树的子图必无圈故e,k的权值必定小于ek,即T2的总权值不大于T1的权值,因T1是最小生成树,故必T2也是最小生成树,但f(T2)>k与k是f函数最大取值矛盾,故T0是最小生成树。

    代码实现的具体过程及思路

    主要就两个过程
    先sort一下, 然后不断的选最小的边来进行扩展, 知道用完所有的边
    要点无非两个:
    1. sort, 使用stl中的sort即可(用的是归并排序, 时间复杂度是ElogE)
    2. 并查集算法, 这个在我以前写的一篇博客中详细介绍了这种算法, 链接如下
    http://blog.csdn.net/fkjslee/article/details/48809903

    复杂度证明

    第一个复杂度来自sort, stl中的归并排序, 复杂度ElogE, 没什么好解释的
    第二个复杂度来自并查集, 并查集的一次查找的复杂度是反阿克曼函数, 近似等于O(1), 一个会查找E* 2次, 所以复杂度是O(E)
    所以总的复杂度是O(ElogE)

    展开全文
  • golang实现prim算法,计算最小生成树 1、题目描述 给定一个n个点m条边无向图,图中可能存在重边和自环,边可能为负数。 求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。 给定一张边带权...

    golang实现prim算法,计算最小生成树

    1、题目描述

    给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。
    
    求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。
    
    给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。
    
    由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。
    
    输入格式
    第一行包含两个整数n和m。
    
    接下来m行,每行包含三个整数u,v,w,表示点u和点v之间存在一条权值为w的边。
    
    输出格式
    共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。
    

    2、数据

    
    数据范围
    1≤n≤500,
    1≤m≤105,
    图中涉及边的边权的绝对值均不超过10000。
    
    输入样例:
    4 5
    1 2 1
    1 3 2
    1 4 3
    2 3 2
    3 4 4
    输出样例:
    6
    

    数据图

    1、初始所有点的距离为正无穷,就是代码中的0x3f3f3f3f等于1061109567

    在这里插入图片描述

    2、以第一个点为最初点,绿色表示选中,进入到最小生成树中

    在这里插入图片描述

    3、以第一个更新其他与之连通的点的距离

    在这里插入图片描述

    4、依次迭代
    在这里插入图片描述

    5、最后的最小生成树

    在这里插入图片描述

    3、朴素prim算法步骤时间复杂度O(n^2)

    1、先初始化所有点距离为正无穷
    2、迭代n次,依次用到集合的最小点更新剩余点距离
    3、将已经确定的点加入到st集合中,st数组为一个bool类型
    

    4、代码实现

    /*
    该图是稠密图,使用邻接矩阵
    */
    package main
    
    import (
       "bufio"
       "fmt"
       "os"
       "strconv"
       "strings"
    )
    
    const (
       N   = 510
       INF = 0x3f3f3f3f
    )
    
    var (
       n, m int
       dist [N]int
       g    [N][N]int
       st   [N]bool
    )
    
    func readLine(r *bufio.Reader) []int {
       s, _ := r.ReadString('\n')
       ss := strings.Fields(s)
       res := make([]int, len(ss))
       for i, v := range ss {
          res[i], _ = strconv.Atoi(v)
       }
       return res
    }
    func prim() int {
       // 初始化距离集合 dist
       for i := 0; i < N; i++ {
          dist[i] = 0x3f3f3f3f
       }
       // 迭代n次
       res := 0 //res 存储最小生成树的大小即边的长度总和
       for i := 0; i < n; i++ {
          // 找到集合外距离最短的点
          t := -1
          for j := 1; j <= n; j++ {
             if !st[j] && (t == -1 || dist[t] > dist[j]) {
                t = j
             }
          }
          // 迭代结束,此时的t就是距离最小点
    
          // 情况一:图上的点不连通,不能组成最小生成树
          if i > 0 && dist[t] == INF {
             return INF
          } // 如果不是第一个点并且最小店的距离是正无穷,则表示图是不连通的
    
          if i > 0 {
             res += dist[t]
          } // 如果不是第一个点,这个t就表示当前点到集合某一个点的最小距离
    
          // 用最小距离点更新其他跟 "现阶段形成的生成树" 的最短距离,
          //注意更新的顺序,自环是不应该被加到最小生成树,所以,为了避免自环加入最小生成树,提前更新res
          for j := 1; j <= n; j++ {
             dist[j] = min(dist[j], g[t][j]) // 此步骤注意是dijkstra的区别,
          }
          st[t] = true
    
       }
       return res
    }
    func min(a, b int) int {
       if a >= b {
          return b
       } else {
          return a
       }
    }
    func main() {
       r := bufio.NewReader(os.Stdin)
       input := readLine(r)
       n, m = input[0], input[1]
       //fmt.Scanf("%d%d\n", &n, &m)
       // 初始化距离
       for i := 0; i < N; i++ {
          for j := 0; j < N; j++ {
             if i == j {
                g[i][j] = 0
             } else {
                g[i][j] = 0x3f3f3f3f
             }
          }
       }
       //
    
       for m > 0 {
          m--
          in := readLine(r)
          a, b, c := in[0], in[1], in[2] //输入
          g[a][b] = min(g[a][b], c)
          g[b][a] = g[a][b] // 无向图
       }
       t := prim()
       if t == INF {
          fmt.Println("impossible")
       } else {
          fmt.Println(t)
       }
    }
    
    展开全文
  • 题意:给出一个n个点m条边图,每个边有权值w,你可以删除一些边,使得剩下的最小生成...我们可以在计算最小生成树时求所有可以加入最小生成树的和,再减去一个最小生成树的和就是答案。 #include<...

    题意:给出一个n个点m条边的图,每个边有权值w,你可以删除一些边,使得剩下的边的最小生成树大小不变并且这个图的最小生成树是独一无二的。现在我们想要知道删除的边的权值和最小是多少?

    思路:要形成独一无二的最小生成树,那么就没有别的边可以在构造最小生成树时加入最小生成树。

    我们可以在计算最小生成树时求所有可以加入最小生成树的边权和,再减去一个最小生成树的边权和就是答案。

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N = 2e5 + 10;
    int n, m, d[N];
    ll ans;
    struct node {
        int u, v, w;
        bool operator <(const node &a)const {
            return w < a.w;
        }
    } no[N];
    int F(int x) {
        return d[x] == x ? x : d[x] = F(d[x]);
    }
    int main() {
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            d[i] = i;
        for(int u, v, w, i = 1; i <= m; i++) {
            cin >> no[i].u >> no[i].v >> no[i].w;
        }
        sort(no + 1, no + m + 1);
        for(int i = 1; i <= m; i++) {
            int j = i;
            while(j <= m && no[i].w == no[j].w)
                j++;
            for(int k = i; k < j; k++) {
                int x = F(no[k].u), y = F(no[k].v);
                if(x != y)
                    ans += no[i].w;
            }
            for(int k = i; k < j; k++) {
                int x = F(no[k].u), y = F(no[k].v);
                if(x != y)
                    d[x] = y, ans -= no[i].w;
            }
        }
        cout << ans << endl;
        return 0;
    }
    

     

    展开全文
  • Kruskal模板:按照边排序,开始从最小边生成树 #include<algorithm> #include<stdio.h> #include<string.h> #include<iostream>...//最小生成树模板(计算最小生成树的sum)...

    Kruskal模板:按照边权排序,开始从最小边生成树

    #include<algorithm>
    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #define N 1000+5//n 个顶点,m条边
    using namespace std;
    //最小生成树模板(计算最小生成树的sum)
    struct node
    {
        int u,v,len;//u->v距离len
    }q[N];
    int f[N],n,m;
    int getf(int v)
    {
        if(f[v]==v)
            return v;//找到祖先
        return f[v]=getf(f[v]);//压缩路径
    }
    bool marge(int u,int v)
    {
        int t1=getf(u),t2=getf(v);
        if(t1==t2)
            return 0;//同一个祖先,已经连接过
        f[t1]=t2;
        return 1;
    }
    bool comp(node a,node b)
    {
        return a.len<b.len;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)//初始化并查集数组
            f[i]=i;//祖先是本身
        for(int i=0;i<m;i++)
            scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].len);
        sort(q,q+m,comp);//按照边的权值从小到大排序
        int count=0,sum=0;
        for(int i=0;i<m;i++)
        {
            if(count==n-1)//n个顶点 n-1条边
                break;
            if(marge(q[i].u,q[i].v))
            {
                count++;
                sum+=q[i].len;
            }
        }
        if(count==n-1)
            printf("%d\n",sum);
        else
            printf("NO\n");
        return 0;
    }
    

    Prim模板:找树顶点和非树顶点之间的最小边

    1、邻接矩阵

    //prim算法
    #include<stdio.h>
    #include<string.h>
    #define N 100+5
    int main()
    {
        int n,m,e[N][N],dis[N];
        bool book[N];
        scanf("%d%d",&n,&m);
        memset(dis,0x3f3f3f3f,sizeof(dis));
        memset(e,0x3f3f3f3f,sizeof(e));
        memset(book,0,sizeof(book));
        for(int i=0;i<N;i++)
            e[i][i]=0;//邻接矩阵
        int u,v,len;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&len);
            e[v][u]=e[u][v]=len;
        }
        for(int i=1;i<=n;i++)
            dis[i]=e[1][i];//初始化dis数组
        /* prim核心 */
        book[1]=1;//标记树顶点
        int count=1,sum=0;//已经加入树的顶点
        while(count<n)//知道顶点全部是树顶点
        {
            int minn=0x3f3f3f3f,j;
            for(int i=1;i<=n;i++)//找到树顶点与非树顶点之间最短的边
            {
                if(dis[i]<minn&&!book[i])
                    j=i,minn=dis[i];
            }
            sum+=minn;
            count++;
            book[j]=1;
            for(int i=1;i<=n;i++)//遍历更新树顶点和非树顶点之间的最短路径
            {
                if(!book[i]&&dis[i]>e[j][i])
                    dis[i]=e[j][i];
            }
        }
        printf("%d\n",sum);
        return 0;
    }
    

    2、邻接表

    次小生成树:

    当给我们求出最小生成树的时候,依次将不属于最小生成树的边(u,v)加入生成树中,此时形成一个环,找出这个环中除了(u,v)最大的边删除,得出的可能是次小生成树,列举所有边,求出次小值.

    最小生成树不唯一:

    输入边的时候记录一下权值相等的边,求最小生成树,判断边是否被标记,如果被标记,依次删除,看是否能生成最小生成树,如果可以,则最小生成树不唯一。poj - 1679

    展开全文
  • 思路:构造最小生成树的时候,直接计算每条可以加进最小生成树的和,然后减掉选中唯一最小生成树的和,并将要选中的最小生成树的点加入点并查集,最后得到ans就是答案。复杂度是O(mlogm)。 ACcode: `...
  • 题目描述 Input Output Example ...一个任务完成时间由最长那条边决定,而要找出最短时间,那么就是计算最大边权最小的生成树,也叫瓶颈树。 理解到这里以后,题目就相当容易了,考虑到K...
  • 题目链接 题目大意 给出一个n个点m条边图,每个边有权值w,你可以删除一些边,使得剩下...我们可以在计算最小生成树时求所有可以加入最小生成树的和,再减去一个最小生成树的和就是答案。 其实真不难理...
  • HDU 4081(最小生成树

    2019-09-25 23:11:27
    题意:给出一个图,每个顶点有一个权值,要求求出一个生成树,这个树上某一边长变为0,...先用prim算法计算最小生成树计算的时候已经在树上点和正在添加点之间路径上最大边就是添加这条边或者和它连边...
  • 正题 ...我们假设能够构成最小生成树的之和为sumsumsum,最小生成树的之和为kkk,都是确定,所以我们剩下任意一颗最小生成树答案都是不变,所以我们计算出sumsumsum和kkk就行了。 ...
  • MST (最小生成树

    千次阅读 2017-08-01 21:37:33
    那么我们需要一种较为高效算法来解决这种问题,这时候,我们就可以学一下MST(最小生成树Kruskal算法了这个算法用到了一些贪心思想,就是我们每次选当前待选最小那条边,如果这条边符合性质,我们就...
  • 最小生成树——kruskal算法和prim算法

    千次阅读 2018-03-07 20:37:36
    在一张带权无向连通图中,各边和最小一颗生成树即为最小生成树。 2.最小生成树应用价值 在现实生活中,很多布线问题,通线网络等问题,都可以直接或者间接转化成最小生成树的问题去给出花费最小方案...
  • 离散数学 习题篇 —— 最小生成树

    千次阅读 2019-12-02 21:37:18
    计算带权无向连通图G的最小生成树。 输入格式: 第一行两个整数:N(1≤N≤300000),表示结点集;表示边条数。 接下来M行,每行表示一条带权边,用3个整数u,v,c表示,分别表示一条边两个端点以及其权值(权值...
  • 在一个无向图中,连接每两个不同顶点每一条边都有一个长度,叫做最小生成树就是在这个图中找到一棵树,这棵树可以把每一个点连接起来,同时保证和是所有生成树中最小。 讲专业点就是这样: 求法 计算...
  • 一个具有n个节点连通图生成树是原图最小连通子集,它包含了n个节点和n-...计算最小生成树的的方法是贪心,则必须满足一下两个条件: 1)不能形成回路; 2)在保证1满足条件下添加尽可能小边。 实现算...
  • poj2031(最小生成树

    2013-02-11 16:01:27
    这题被分到计算几何中了,是挺简单的最小生成树,把细胞当成图中点,各点之间 = 细胞间距离-两细胞半径 再套最小生成树的模板就OK了 #include #include #include #include #include #include ...
  • 题目大意 求生成树,使得:∑e∈ET|w(e)...首先来看最小方差生成树,方差可以写成平方和平均值减去和平方,因此可以快速计算一些数字方差; 考虑,由于所有数字和是O(nw)O(nw)O(nw),所以平均值也是这个...
  • 把一个连通无向图生成树边按权值递增排序,称排好序列表为有序边列表,则任意两棵最小生成树的有序边列表是相同。(算法导论23.1-8) 通过这个性质,考虑边相同边,把这些边中能够替代计算...
  • 我们考虑在计算最小生成树的时候,将两个联通块合并时,我们会选择连接这两个联通块最小边。 那么我们就可以让每个联通块合并时,让其他边都是比这个给出边边+1就好了。 codecodecode #include&lt;...
  • 算法:最小生成树MST

    2019-05-27 23:28:58
    用堆维护边,最小权边优先考虑。 并查集加速联通分量判断。 例题:ZOJ1203,POJ1861,POJ1251,POJ2031,POJ2421 普里姆: 贪心思想,适合稠密图,O(N*N) 维护一个长度为N数组,保存当前可到达点最短距离,若...
  • Kruscal求最小生成树用到知识:图结构体、按边排序、并查集(不产生回路) 但是这道题仍然需要精心思考,原因是有一些边是“已经存在”,那么在计算最小生成树成本时候应该只考虑未修成边。 要...
  • 5163 -- 【11.04题目】玩游戏 ...小B定义一条路径权值为所有经过边中最大权值,小A则定义两点最短路径为所有路径中权值最小的路径。 每次小A先选出两个点m1,m2,然后小B选出两个点b1,b2,计算出它们...
  • 分析: 根据最小生成树的性质,...对于权值相同的一个边集,用爆搜讨论完所有的选择情况,如果选择完后,这种权值边的总数,与预先求出的最小生成树中这种边权的边数量相同,即合法。 然后乘法原理乘起来就可以...
  • 最小生成树----Prim算法

    千次阅读 2009-07-31 08:33:00
    最小生成树是数据结构中图一种重要应用,它要求是从一个带权无向完全图中选择n-1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树的权最小。 以下代码包含生成无向网图,prim算法计算最小生成树...
  • 题意:有N个城市,其中M个城市有卫星频道,两个有卫星城市无论多远都能联系,而两个没有城市只在一定距离内...思路:求一颗最小生成树,去掉生成树里最大M条边,计算剩下边最大。 #include #include
  • 本来以为是一道计算几何,然后看大佬代码发现竟然是最小生成树?? 能想到最小生成树很诡异,建图也很诡异。 最后相当于求0-n+1这条路上最大边。 列数就是该点横坐标。 建完图套一下Krustra板子就好了。...
  • 源自大白书 题意 有n座城市通过m条...解: 首先求出最小生成树,并把它改写成有根树,让fa[i]和cost[i]分别表示节点i父亲编号和它与父亲之间,L[i]表示节点i深度,接下来通过预处理计算出数组anc 和 maxc...
  • 思路:先求出每两个城市间距离,也就是边,然后用kruscal来求最小生成树,得出最小值。 注意输出格式,要求每两个输出之间要有一个空行。但是最后一个输出后面不能有空行,所以判断是不...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 126
精华内容 50
关键字:

最小生成树权的计算