精华内容
下载资源
问答
  • sdut 2494 统计最小生成树的个数

    千次阅读 2012-12-05 14:54:16
    给你一图,该图可能存在很多最小生成树。求最小生成树可能包含的边的个数。 思路: 这里我们将权值相同的边看成一块,按块来处理。 按krusal的算法处理,检查每一块当该边加入后最小生成树后不会形成环就+1, ...
    /*
    题意:
    给你一个图,该图可能存在很多最小生成树。求最小生成树可能包含的边的个数。
    
    思路:
    这里我们将权值相同的边看成一个块,按块来处理。
    按krusal的算法处理,检查每一块当该边加入后最小生成树后不会形成环就+1,
    这里我们先不把他们加入,检查完后再将边加入,这样就能保证可能加入最小生成树的相同的权值的边都加入了,并且我们也计数了。
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=100002;
    int n,m,father[maxn],ans,sum,x,y;
    struct node
    {
        int u,v,cost;
    }p[500007];
    int cmp(node a,node b)
    {
        return a.cost<b.cost;
    }
    int find(int x)
    {
        if (x != father[x])
        father[x]=find(father[x]);
        return father[x];
    }
    int main()
    {
         int i,j,k,u,v;
         //freopen("din.txt","r",stdin);
         while(scanf("%d%d",&n,&m)!=EOF)
         {
             ans=sum=0;
             for(i=1;i<=n;i++)father[i]=i;
             for(i=1;i<=m;i++)
             {
                 scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].cost);
             }
             sort(p+1,p+m+1,cmp);
             for(i=1;i<=m;i=j)
             {
                for(j=i;j<=m;j++)
                {
                     if(p[i].cost!=p[j].cost)break;
                  x=find(p[j].u),y=find(p[j].v);
                  if(x!=y)
                  {
                        ans++;
                  }
                }
                for(k=i;k<j;k++)
                {
                     x=find(p[k].u),y=find(p[k].v);
                      father[x]=y;
                }
             }
                        printf("%d\n",ans);
            }
        return 0;
    }
    

    展开全文
  • Problem Description 在图论中,树:任意两顶点间有且只有一条路径的图。 生成树:包含了图中所有顶点的一种树。 最小生成树:对于连通的带权图(连通网)G...但是,对于一图而言,最小生成树并不是唯一的。 现

    Problem Description

    在图论中,树:任意两个顶点间有且只有一条路径的图。

    生成树:包含了图中所有顶点的一种树。

    最小生成树:对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,权最小的生成树称为G的最小生成树(Minimum Spanning Tree)。最小生成树可简记为MST。

    但是,对于一个图而言,最小生成树并不是唯一的。

    现在,给你一个连通的有权无向图,图中不包含有自环和重边,你的任务就是寻找出有多少条边,它至少在一个最小生成树里。图保证连通。

     Input

    输入数据第一行包含一个整数T,表示测试数据的组数。对于每组测试数据:

    第一行包含两个整数n,m(1<n<100000,n-1<m<100000),接下来m行,每行三个整数a,b,v(1<=a,b<=n,1<v<500),表示第i条路线连接景点A和景点B,距离是V。两个数字之间用空格隔开。

     Output

    对于每组测试数据,输出一行,包含一个整数,表示满足条件的边的个数。

     Sample Input

    14 51 2 1011 3 1002 3 22 4 23 4 1

     Sample Output

    4

     Source

    福州大学第九届程序设计竞赛

    解题思路:

    一棵树可以有多个最小生成树,但是他们的权值一定是相等的。按权值从小到大对边排序,然后把权值相同的边归为一组,判断时候,只要一个边的两个端点不在同一个集合,那么该边就可以加入到最小生成树里面。

    代码:

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    const int maxn=100005;
    const int maxm=100005;
    int n,m;
    int parent[maxn];
    
    struct Node
    {
        int from,to,w;
    }node[maxm];
    
    void init(int n)
    {
        for(int i=1;i<=n;i++)
            parent[i]=i;
    }
    
    int find(int x)
    {
        if(parent[x]==x)
            return x;
        else
            return parent[x]=find(parent[x]);
    }
    
    bool same(int x,int y)
    {
        return find(x)==find(y);
    }
    void unite(int x,int y)
    {
        parent[find(x)]=find(y);
    }
    
    bool cmp(Node a,Node b)
    {
        return a.w<b.w;
    }
    
    void solve()
    {
        int cnt=0;
        int i,j;
        for(i=1;i<=m;i=j)
        {
            for(j=i;node[j].w==node[i].w;j++)//只要相同权值的边两个端点不在同一个集合,该边就一定存在一个最小生成树里面
            {
                if(!same(node[j].from,node[j].to))
                    cnt++;
            }
            for(j=i;node[j].w==node[i].w;j++)//有回路的边加上不影响后面的加边
                unite(node[j].from,node[j].to);
        }
        printf("%d\n",cnt);
    }
    
    int main()
    {
        int t;scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            init(n);
            for(int i=1;i<=m;i++)
                scanf("%d%d%d",&node[i].from,&node[i].to,&node[i].w);
            sort(node+1,node+1+m,cmp);
            solve();
        }
        return 0;
    }
    


    展开全文
  • 最小生成树(MST)算法可以生成多相等最小的MST,但是MST程序通常仅报告一任意选择的MST。 同样,大多数MST程序也不提供统计指标来支持他们估计的MST的可信度。 MSTgold估计替代MST的数量,报告用户确定的那些树...
  • 数据结构 最小生成树 Kruskal算法

    千次阅读 2017-06-25 10:30:14
    数据结构 最小生成树 Kruskal算法 无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树,对连通图的不同遍历,就可能得到不同的生成树,那么,它的所有...

    数据结构 最小生成树 Kruskal算法

    无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树,对连通图的不同遍历,就可能得到不同的生成树,那么,它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵生成树为最小生成树,简称为最小生成树

    最小生成树:
    具有最小权重且连接到所有结点的树

    对于带权无向图G=(V, E),V表示图中的结点,E表示图中的边,最小生成树为集合T, T是以最小代价连接V中所有顶点所用边E的最小集合(就是联通图G中所有结点所需要的边长度总和最小)。 集合T中的边能够形成一颗树,因为每个节点(除根节点)都能向上找到它的一个父节点,这些边加上V就构成图G的一颗最小生成树

    安全边:
    假设A是某棵最小生成树的子集,下一步我们需要做的就是找出一条边(u,v),将其加入到A中,使得A∪{(u,v)}也是某棵最小生成树的子集,我们称(u,v)为安全边
    切割(S,V-S):
    —对集合V的一个划分,将集合V划分为两个部分S和V-S
    横跨切割:
    —若边(u,v)的一个节点属于S另一个节点属于V-S,则称(u,v)横跨切割
    尊重集合A:
    如果A中不存在横跨切割的边,则称该集合尊重集合A

    横跨尊重集合A的切割(S,V-S)的一条轻量级边(u,v)为A的一条安全边

    Prim算法和Kruskal算法在实现方面的区别:
    1、Kruskal算法在生成最小生成树的过程中产生的是森林,
    Prim算法在执行过程中始终都是一棵树;
    2、Kruskal和Prim实现上的最大区别:
    Kruskal不需要搜索每个顶点的邻接节点,
    Prim图构建时需要利用邻接链表进行构建,Kruskal不用!
    3、Kruskal算法在效率上要比Prim算法快,
    Kruskal只需要对权重边做一次排序
    而Prim算法则需要做多次排序

    Prim算法是依赖于点的算法:
    它的基本原理是从当前点寻找一个离自己(集合)最近的点然后把这个点拉到自己家来(距离设为0),同时输出一条边,并且刷新到其他点的路径长度。俗称,刷表。
    根据Prim算法的特性可以得知,它很适合于点密集的图。对Prim算法通常采用邻接矩阵的储存结构。这种储存方法空间复杂度N^2,时间复杂度N^2。
    对于稍微稀疏一点的图,其实我们更适合采用邻接表的储存方式,可以节省空间,并在一定条件下节省时间。

    Kruskal算法是依赖边的算法:
    基本原理是将边集数组排序,然后通过维护一个并查集来分清楚并进来的点和没并进来的点,依次按从小到大的顺序遍历边集数组,如果这条边对应的两个顶点不在一个集合内,就输出这条边,并合并这两个点。

    根据Kruskal算法的特性可得,在边越少的情况下,Kruskal算法相对Prim算法的优势就越大。同时,因为边集数组便于维护,所以Kruskal在数据维护方面也较为简单,不像邻接表那样复杂。Kruskal算法的速度与点数无关,对于稀疏图可以采用Kruskal算法。

    Kruskal算法(克鲁斯卡尔算法)

    算法原理:
    首先将每个顶点放入其自身的数据集合中。然后,按照权值的升序来选择边。当选择每条边时,判断定义边的顶点是否在不同的数据集中。如果是,将此边插入最小生成树的集合中,同时,将集合中包含每个顶点的联合体取出,如果不是,就移动到下一条边。重复这个过程直到所有的边都探查过

    Kruskal在找最小生成树结点之前,需要对所有权重边做从小到大排序。将排序好的权重边依次加入到最小生成树中,如果加入时产生回路就跳过这条边,加入下一条边。当所有结点都加入到最小生成树中之后,就找出了最小生成树

    算法描述:
    1、新建图G,把图G中所有的边按照权值从小到大排序。(一般使用优先队列)
    2、取出最小的边,如果这条边连接的两个节点于图G中不在同一个连通分量中,则添加这条边到图G中.(使用并查集)
    3、重复步骤2,直至图G中所有的节点都在同一个连通分量中

    性能分析
    Kruskal算法,基本上取决于优先队列的选择,以及并查集的实现。
    算法效率为 O(ElogE) E为图中的边数

    时间复杂度:O(Elog2E) E为图中的边数
    //对优先队列和并查集 //查找算法之顺序、二分、二叉搜索树、红黑树 和并查集

    import java.io.IOException;
    import java.util.Scanner;
    
    public class Kruskal {
        private int mEdgNum;        // 边的数量
        private char[] mVexs;       // 顶点集合
        private int[][] mMatrix;    // 邻接矩阵
        private static final int INF = 100;//Integer.MAX_VALUE;   // 最大值
    
        //创建图(用已提供的矩阵)
        public Kruskal(char[] vexs, int[][] matrix) {// vexs-- 顶点数组 ,matrix-- 矩阵(数据)        
            // 初始化"顶点数"和"边数"
            int vlen = vexs.length;
            // 初始化"顶点"
            mVexs = new char[vlen];
            for (int i = 0; i < mVexs.length; i++)
                mVexs[i] = vexs[i];
            // 初始化"边"
            mMatrix = new int[vlen][vlen];
            for (int i = 0; i < vlen; i++)
                for (int j = 0; j < vlen; j++)
                    mMatrix[i][j] = matrix[i][j];
            // 统计"边"
            mEdgNum = 0;
            for (int i = 0; i < vlen; i++)
                for (int j = i+1; j < vlen; j++)
                    if (mMatrix[i][j]!=INF)
                        mEdgNum++;
        }
    
        //返回ch位置
        private int getPosition(char ch) {
            for(int i=0; i<mVexs.length; i++)
                if(mVexs[i]==ch)
                    return i;
            return -1;
        }
    
        // 返回顶点v的第一个邻接顶点的索引,失败则返回-1
        private int firstVertex(int v) {
            if (v<0 || v>(mVexs.length-1))
                return -1;
            for (int i = 0; i < mVexs.length; i++)
                if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF)
                    return i;
            return -1;
        }
    
        //打印邻接顶点的索引、权重
        private void nextVertexs() {
            for(int v = 0; v < mVexs.length; v++){
                System.out.print("\n结点"+v);
                for (int i = 0; i < mVexs.length; i++) {
                   if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF)
                      System.out.print("邻接点"+i+"(权重"+mMatrix[v][i]+")");
                }
            } 
        }
    
        //打印矩阵队列图
        public void print() {
            int i, j, sum;
            System.out.printf("结点表:");
            for (i=0; i < mVexs.length; i++) { 
                sum = 0;
                for (j=0; j < mVexs.length; j++) { 
                   if (mMatrix[i][j]!=0 && mMatrix[i][j]!=INF) {
                      sum++;
                   }
                }
                System.out.print("\n结点"+i+", 标识"+mVexs[i]+", 共有邻接点"+sum);
            }
    
            System.out.print("\n\n");
            System.out.printf("邻接矩阵:\n");
            for (i = 0; i < mVexs.length; i++) {
                for (j = 0; j < mVexs.length; j++)
                    System.out.printf("%3d ", mMatrix[i][j]);
                System.out.printf("\n");
            }
    
            nextVertexs();
        }
    
        /*
         * 克鲁斯卡尔(Kruskal)最小生成树
         */
        public void kruskal() {
            int index = 0;                      // rets数组的索引
            int[] vends = new int[mEdgNum];     // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
            EData[] rets = new EData[mEdgNum];  // 结果数组,保存kruskal最小生成树的边
            EData[] edges;                      // 图对应的所有边
    
            edges = getEdges(); // 获取"图中所有的边"
            sortEdges(edges, mEdgNum); // 将边按照"权"的大小进行排序(从小到大)
    
            for (int i=0; i<mEdgNum; i++) {
                int p1 = getPosition(edges[i].start);      // 获取第i条边的"起点"的序号
                int p2 = getPosition(edges[i].end);        // 获取第i条边的"终点"的序号
    
                int m = getEnd(vends, p1);                 // 获取p1在"已有的最小生成树"中的终点
                int n = getEnd(vends, p2);                 // 获取p2在"已有的最小生成树"中的终点
                // 如果m!=n,意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
                if (m != n) {
                    vends[m] = n;                       // 设置m在"已有的最小生成树"中的终点为n
                    rets[index++] = edges[i];           // 保存结果
                }
            }
    
            // 统计并打印"kruskal最小生成树"的信息
            int length = 0;
            for (int i = 0; i < index; i++)
                length += rets[i].weight;
    
            System.out.printf("\nKruskal=%d: ", length);
            for (int i = 0; i < index; i++)
                System.out.printf("(%c,%c) ", rets[i].start, rets[i].end);
            System.out.printf("\n");
        }
    
        //获取图中的边
        private EData[] getEdges() {
            int index=0;
            EData[] edges;
            edges = new EData[mEdgNum];
            for (int i=0; i < mVexs.length; i++) {
                for (int j=i+1; j < mVexs.length; j++) {
                    if (mMatrix[i][j]!=INF) {
                        edges[index++] = new EData(mVexs[i], mVexs[j], mMatrix[i][j]);
                    }
                }
            }
            return edges;
        }
    
        //对边按照权值大小进行排序(由小到大)
        private void sortEdges(EData[] edges, int elen) {
            for (int i=0; i<elen; i++) {
                for (int j=i+1; j<elen; j++) {
                    if (edges[i].weight > edges[j].weight) {// 交换"边i"和"边j"
                        EData tmp = edges[i];
                        edges[i] = edges[j];
                        edges[j] = tmp;
                    }
                }
            }
        }
    
        //获取i的终点
        private int getEnd(int[] vends, int i) {
            while (vends[i] != 0)
                i = vends[i];
            return i;
        }
    
        // 边的结构体
        private static class EData {
            char start; // 边的起点
            char end;   // 边的终点
            int weight; // 边的权重
            public EData(char start, char end, int weight) {
                this.start = start;
                this.end = end;
                this.weight = weight;
            }
        };
    
    
        public static void main(String[] args) {
            char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
            int matrix[][] = {
                     /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
              /*A*/ {   0,  12, INF, INF, INF,  16,  14},
              /*B*/ {  12,   0,  10, INF, INF,   7, INF},
              /*C*/ { INF,  10,   0,   3,   5,   6, INF},
              /*D*/ { INF, INF,   3,   0,   4, INF, INF},
              /*E*/ { INF, INF,   5,   4,   0,   2,   8},
              /*F*/ {  16,   7,   6, INF,   2,   0,   9},
              /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
            Kruskal pG;
            pG = new Kruskal(vexs, matrix);
    
            pG.print();   // 输出图的有关信息
    
            pG.kruskal();   // Kruskal算法生成最小生成树
        }
    }

    程序输出:

    结点表:
    结点0, 标识A, 共有邻接点3
    结点1, 标识B, 共有邻接点3
    结点2, 标识C, 共有邻接点4
    结点3, 标识D, 共有邻接点2
    结点4, 标识E, 共有邻接点4
    结点5, 标识F, 共有邻接点5
    结点6, 标识G, 共有邻接点3

    邻接矩阵:
    0 12 100 100 100 16 14
    12 0 10 100 100 7 100
    100 10 0 3 5 6 100
    100 100 3 0 4 100 100
    100 100 5 4 0 2 8
    16 7 6 100 2 0 9
    14 100 100 100 8 9 0

    结点0邻接点1(权重12)邻接点5(权重16)邻接点6(权重14)
    结点1邻接点0(权重12)邻接点2(权重10)邻接点5(权重7)
    结点2邻接点1(权重10)邻接点3(权重3)邻接点4(权重5)邻接点5(权重6)
    结点3邻接点2(权重3)邻接点4(权重4)
    结点4邻接点2(权重5)邻接点3(权重4)邻接点5(权重2)邻接点6(权重8)
    结点5邻接点0(权重16)邻接点1(权重7)邻接点2(权重6)邻接点4(权重2)邻接点6(权重9)
    结点6邻接点0(权重14)邻接点4(权重8)邻接点5(权重9)

    Kruskal=36: (E,F) (C,D) (D,E) (B,F) (E,G) (A,B)

    展开全文
  • 解决最小生成树MST的两算法

    千次阅读 2018-08-24 20:29:15
    最小生成树:在N顶点的图中选择N-1条边构成一极小连通子图,使该极小连通子图的所有边权之和最小,称其为该图的最小生成树。求解图的最小生成树算法有常用的两。 Prim算法: 普林算法是依赖点的算法,从点的...

    最小生成树:在N个顶点的图中选择N-1条边构成一个极小连通子图,使该极小连通子图的所有边权之和最小,称其为该图的最小生成树。求解图的最小生成树算法有常用的两个。

    Prim算法

    普林算法是依赖点的算法,从点的方面去考虑构成一颗最小生成树,基本思想是:假设有图G,顶点集合U,先从U中任意选出一点进入集合V。再从U-V中选出一点使其到V中任意一点的权值最小,将该点也加入到V;继续依此重复从U-V中挑选点进入集合V中直至N个点全部完毕,此时构建出了具有N-1条边图的MST。如果N个点中有无法标记的点,那说明无法形成最小生成树。

    Kruskal算法:

    克鲁斯科尔算法是依赖于边的算法,按图中边权值从小到大进行排序,如果选择该边后不形成回路则保留这一条边,形成回路则删除该边,依次选择够n-1条边则完成改图的MST。判断是否形成回路的方式是维护一个并查集,将由边关联的点都放入并查集内,祖先相同证明它们都直接或间接的于同一点相连会形成回路,祖先不同则不会形成回路。如果被选择的边无法到达n-1条,那么说明无法形成最小生成树。

    区别:

    prim算法适用于点密集的情形,时间复杂度为O(N^2),适用于稠密图,而通过实现知道kruskal只需通过对e条边一次排序,其时间复杂度为O(eloge)

     

     

    Eddy's picture

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
    Total Submission(s): 12076    Accepted Submission(s): 6063

    Problem Description

    Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result it can be imagined, the friends are not interested in his picture.Eddy feels very puzzled,in order to change all friends 's view to his technical of painting pictures ,so Eddy creates a problem for the his friends of you.
    Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally to link in the same place. How many distants does your duty discover the shortest length which the ink draws?

    Input

    The first line contains 0 < n <= 100, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point. 

    Input contains multiple test cases. Process to the end of file.

    Output

    Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the points. 

    Sample Input

    3

    1.0 1.0

    2.0 2.0

    2.0 4.0

    Sample Output

    3.41

    裸的最小生成树问题,给出各点坐标需计算出所有边的权值。

    可知边的个数很多点很密集,可以使用普林算法。

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    #define inf 0x3f3f3f3f
    int flag[101];                            //标记数组
    double map[101][101], box[101];           //map数组用来存放所有点之间的边权值,box数组维护到角标序号这个点的最短距离
    int n;
    double prime()
    {
    	double res = 0;
    	int now = 1;                      //初始可以从任意点开始,选择第一个点
    	for (int i = 1; i <= n; i++)
    		box[i] = map[now][i];
    	for (int i = 2; i <= n; i++)
    	{
    		double minn = inf;
    		for (int j = 2; j <= n; j++)
    		{
    			if (!flag[j] && box[j] < minn)     //从剩下未标记点中选择边权最小的
    			{
    				minn = box[j];
    				now = j;                  //将该点拿出并标记
    			}
    		}
    		flag[now] = 1;
    		res += minn;
    		for (int j = 2; j <= n; j++)      //更新box数组,如果新点到剩下点的距离小于box的记录值,则更新
    		{
    			if (!flag[j] && map[now][j] < box[j])
    				box[j] = map[now][j];
    		}
    	}
    	return res;
    }
    int main()
    {
    	while (scanf("%d", &n) != EOF)
    	{
    		memset(flag, 0, sizeof(flag));
    		pair <double, double> p[101];     //记录的点的坐标通常是一对,经常使用pair容器储存
    		for (int i = 1; i <= n; i++)
    			cin >> p[i].first >> p[i].second;
    		for (int i = 1; i <= n; i++)
    		{
    			for (int j = 1; j <= n; j++)
    				map[i][j] = sqrt(pow((p[i].first - p[j].first), 2) + pow((p[i].second - p[j].second), 2));       //计算所有点之间的边权
    		}
    		double res = prime();
    		printf("%.2f\n", res);
    	}
    	return 0;
    }

    继续畅通工程

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 29333    Accepted Submission(s): 12339

    Problem Description

    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。

    Input

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。

    当N为0时输入结束。

    Output

    每个测试用例的输出占一行,输出全省畅通需要的最低成本。

    Sample Input

    3

    1 2 1 0

    1 3 2 0

    2 3 4 0

    3

    1 2 1 0

    1 3 2 0

    2 3 4 1

    3

    1 2 1 0

    1 3 2 1

    2 3 4 1

    0

    Sample Output

    3 1 0

    可知各个点之间都有边权,如果已经修建好公路的话边权即为零。可以使用kruskal算法

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    struct node
    {
    	int x, y, cast, z;
    }map[10000];
    int fa[10000], n;
    int cmp(node a, node b)
    {
    	return a.cast < b.cast;
    }
    int getfa(int h)                         //并查集操作
    {
    	if (h == fa[h])
    		return h;
    	return fa[h] = getfa(fa[h]);
    }
    bool merge(int u, int v)
    {
    	int t1 = getfa(u), t2 = getfa(v);
    	if (t1 != t2)
    	{
    		fa[t1] = t2;
    		return true;
    	}
    	return false;
    }
    int main()
    {
    	while (scanf("%d", &n) != EOF)
    	{
    		if (n == 0)
    			break;
    		int k = 0, res = 0;
    		for (int i = 1; i <= n; i++)     //并查集初始化
    			fa[i] = i;
    		for (int i = 0; i < n*(n-1)/2; i++)
    		{
    			scanf("%d%d%d%d", &map[i].x, &map[i].y, &map[i].cast, &map[i].z);
    			if (map[i].z == 1)
    				map[i].cast = 0;
    		}
    		sort(map, map + n*(n-1)/2, cmp); //一次排序,按边权从从小到大
    		for (int i = 0; i < n*(n - 1) / 2; i++)
    		{
    			if (merge(map[i].x, map[i].y))
    			{
    				res += map[i].cast;          //如果加入这条边不形成回路则保留
    				k++;
    			}
    			if (k == n - 1)
    				break;
    		}
    		cout << res << endl;
    	}
    }

     

    展开全文
  • 最小生成树的邻接矩阵实现

    千次阅读 2014-09-02 17:50:23
    求上面这图的最小生成树
  • 10分钟学会最小生成树(Prim+Kruskal)

    千次阅读 2020-05-09 09:43:18
    最小生成树 ​ Minimal Spanning Trees (MST) ​ 任何只由图G的边构成,并包含G的所有顶点的树称为G的生成树 ​ 加权无向图G的生成树的权重是该生成树的所有边的权重之和 ​ 最小生成树是其所有生成树中权重最小的...
  • Kuangbin Flying 6最小生成树专题

    千次阅读 2015-01-29 12:56:53
    kuangbin带你飞系列专题六最小生成树题解报告
  • 克鲁斯卡尔算法生成最小生成树

    千次阅读 2020-02-22 17:05:23
    1)克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。 2)基本思想:按照权值从小到大的顺序选择 n-1条边,并保证这 n-1条边不构成回路 3)具体做法:首先构造一只含 n顶点的森林,然后依权值从小...
  • 由生成树定义可知,无向连通图的生成树不是唯一 的,于是最小生成树的定义诞生,即:无向连通图是一带权图,她的所有生成树中必有一棵边的权值总和最小的生成树(称为:最小代价生成树,即:最小生成树) ...
  • 文章目录最小生成树Kruskal算法Prime算法并查集三操作具体题目path compression和union by rank参考资料 最小生成树 说道并查集,不得不提的是最小生成树,因为并查集的最经典的应用就是解决最小生成树的Kruskal...
  • 数据结构之最小生成树 Kruskal算法

    千次阅读 2015-11-08 21:33:58
    1. 最小生成树  2. 克鲁斯卡尔算法介绍  3. 克鲁斯卡尔算法图解  4. 克鲁斯卡尔算法分析  5. 克鲁斯卡尔算法的代码说明  6. 克鲁斯卡尔算法的源码 转载请注明出处:...
  • 判断最小生成树是否唯一

    千次阅读 2018-10-25 09:07:24
    在最小生成树的推论中,生成树一定包含连接两森林中间权值最小的边,所以在做最小生成树的同时统计这些备选边,若备选边大于所需的,则不唯一。 #include&lt;bits/stdc++.h&gt; #define f(i,l,r) for(i=...
  • 数据结构之最小生成树

    千次阅读 2016-07-08 21:38:21
    现在,设置两新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边。 从所有uЄU,vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入...
  • 数据结构 最小生成树(prime算法)

    千次阅读 2019-04-10 16:08:23
    实验十四、最小生成树 1 实验目的 本实验实现最小生成树的prime算法。 2 实验内容 建立如图所示的邻接矩阵; 2)根据prime算法求其最小生成树,如从顶点A出发生成的最小生成树为: 利用前缀点数组...
  • 建立通信(最小生成树

    千次阅读 2018-05-08 19:36:19
    据不完全统计,受地震影响,四川大部分灾区通信陷入瘫痪,基站因断电、传输中断等原因退出服务,目前总公司已紧急部署对受灾地区进行通信抢修。按照应急通信保障预案,必须尽快、付出代价最小,效率更高来全力...
  • Java: Kruskal算法生成最小生成树(邻接矩阵): package com.neusoft.data.structure; /** * Java: Kruskal算法生成最小生成树(邻接矩阵) * 克鲁斯卡尔(Kruskal)算法 * K...
  • 三、加到n-1条边,则结束循环,就会生成该图的最小生成树 伪代码如下: 现在的问题就是,如何判断是否有环路呢? 我们使用并查集的方法来判断,用二叉树实现并查集。查 即: 就是 fin...
  • ACM-最小生成树之畅通工程——hdu1863

    千次阅读 2014-05-25 11:04:41
    ACM 最小生成树 Kruskal Prim 畅通工程 hdu1863
  • 最小生成树不仅可以得到最小的权值之和,其最大边权为生成树中最大边权最小的。*一道例题:1:承包池塘的青蛙 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 128000kB 描述 某池塘有N片荷叶, M只青蛙, 青蛙...
  • 最小生成树 , Prime 算法

    千次阅读 多人点赞 2018-07-27 14:21:20
    最小生成树 Prime算法 题上会先给你说几村庄,或者几点,然后给你几句话,这几句话就是点到点之间的距离,然后你没有钱,但是你想修路,所以呢,你必须找到一最省钱的方法,把每地方给连通起来,就比如...
  • 数据结构课设--7最小生成树问题

    千次阅读 2019-09-24 00:20:45
    如何以最低的经济代价建设这通信网,是一网的最小生成树问题。 【系统要求】 1.利用克鲁斯卡尔算法求网的最小生成树。 2.利用普里姆算法求网的最小生成树。 3.要求输出各条边及它们的权值。 【测试数据】 由...
  • ACM 最小生成树 继续畅通工程 hdu1879 Kruskal
  • 算法竞赛中常用的算法,求图的最小生成树 过程: 对边集排序, 选取最小边,将连接的节点放到一集合中 选取次小的边,当边连接的定点不在同一集合中时,合并集合。#include #include #include #include ...
  • 非常裸的最小生成树,基本已经熟悉prim的代码了
  • 并查集和最小生成树

    千次阅读 2018-03-23 15:53:10
    2.性质:并查集算法(union_find sets)不支持分割一集合,可求连通子图、求最小生成树。 3.引例:杭电HDU1232畅通工程 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。...
  • 最小生成树问题【PAT】

    千次阅读 2014-04-01 23:28:56
    8-06. 畅通工程之局部最小花费问题  时间限制  ...某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两城镇间都可以实现快速交通(但不
  • hdu1863 畅通工程(判定最小生成树

    千次阅读 2015-07-23 15:51:47
    畅通工程 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 20662 Accepted Submission(s): 8857 ...省政府“畅通工程”的目标是使全省任何两
  • Kruskal(克鲁斯卡尔) 最小生成树 算法详解+模板

    万次阅读 多人点赞 2017-07-26 15:27:58
    最小生成树在含有n顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树。 例如,对于如上图G4所示的连通网可以有多棵权值总和不相同...
  • 畅通工程 ...经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成本。   Input 测试输入包含若干测试用例。每测试用例的第1行给出

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,015
精华内容 22,006
关键字:

统计最小生成树个数