精华内容
下载资源
问答
  • 判断最小生成树是否唯一

    千次阅读 2019-04-16 17:08:50
    题目链接 题目描述:给一个图,判断最小生成树...不唯一定义:如果最小生成树的其中一条边或者几条边可以被其他边所取代,最后生成的最小生成树权重一样,就表明最小生成树唯一。这个取代过程,怎样控制?直接的...

    题目链接

    题目描述:给一个图,判断最小生成树是否唯一,n<=100

    解题思路:题意简单明了,最小生成树模板都会敲,网上也没有什么特别好的方法,都是最简单暴力枚举,枚举的前提,有可以取代它的边。

    最小生成树特征:n个节点,n-1条边。

    不唯一定义:如果最小生成树的其中一条边或者几条边可以被其他边所取代,最后生成的最小生成树权重一样,就表明最小生成树不唯一。这个取代过程,怎样控制?直接的方法,标识,把最小生成树所有的边都标识。然后枚举去掉标识中一条边,构造出的最小生成树是否和最小生成树权重一样。但是很显然,我们做了很多无用功,有一些边是无法取代的,怎么判断哪些边是无法取代的?最简单的方法,能否找到一个权重一样的边来取代它。如果有一条权重一样,则去掉这条边,构造最小生成树,这就是枚举的过程。

    #include<stdio.h>
    #include<algorithm>
    #include <vector>
    using namespace std;
    #include <string.h>
    int book[110];
    int n,m,father[110];
    struct  node
    {
        int x;
        int y;
        int value;
    } Q[11000];
    bool cmp(node a,node b)
    {
        return a.value<b.value;
    }
    void init()
    {
        for(int i=0; i<=n; i++)
            father[i] = -1;
    }
    int find(int x)
    {
        if(father[x]==-1)
            return x;
        return father[x]=find(father[x]); //这个点可能造成超时
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d %d",&n,&m);
            memset(book,0,sizeof(book));
            for(int i=0; i<m; i++)
                scanf("%d %d %d",&Q[i].x,&Q[i].y,&Q[i].value);
            sort(Q,Q+m,cmp);
            init();
            int  kmp = 0,tmp = 0,flag=0;
            for(int i=0; i<m; i++)
            {
                int tx = find(Q[i].x);
                int ty = find(Q[i].y);
                if(tx!=ty)
                {
                    father[tx] = ty;
                    tmp += Q[i].value;
                    book[i] = 1 ;
                    kmp++;
                }
                if(kmp == n -1)
                    break;
            }
            for(int i=0; i<m; i++)
            {
                if(book[i]==1&&Q[i+1].value==Q[i].value&&i+1<m)
                {
                    init();
                    int kmp =0,term = 0;
                    for(int j=0; j<m; j++)
                    {
                        if(i==j) continue;
                        int tx = find(Q[j].x);
                        int ty = find(Q[j].y);
                        if(tx!=ty)
                        {
                            father[tx]=ty;
                            term += Q[j].value;
                            kmp++;
                        }
                        if(kmp==n-1)
                            break;
                    }
                    if(term == tmp)
                    {
                        flag=1;
                        break;
                    }
                }
            }
            if(flag)
                printf("Not Unique!\n");
            else printf("%d\n",tmp);
        }
        return 0;
    }
    

     

    展开全文
  • 最小生成树是图论的经典问题,求最小生成树以及求最小生成树的权值和得到了足够关注,而很少人去研究最小生 成树是否唯一。对于给定的图而言,因为最小生成树的权值和是确定的,所以最小生成树唯一当且仅当最小生成树...
  • 1、最小生成树是否唯一算法  给定一无向图,判断最小生成树是否唯一。 2、思路  先求出最小生成树,记录结果,依次删除树中各边,再求最小生成树,看与最初结果是否相同,若相同则不唯一。 3、代码实现 #...

    1、最小生成树是否唯一算法

            给定一无向图,判断最小生成树是否唯一。

    2、思路

           先求出最小生成树,记录结果,依次删除树中各边,再求最小生成树,看与最初结果是否相同,若相同则不唯一。

    3、代码实现

    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <queue>
    #include <stack>
    #include <vector>
    
    using namespace std;
    
    const int N = 109;
    const int MAX = 100000000;
    int d[N];
    int g[N][N];
    int fa[N];
    pair<int, int> v[N];
    
    int prim(int n, int m, bool f)
    {
        for(int i=0;i<n;i++)
        {
            d[i] = g[0][i];
            fa[i] = 0;
        }
        d[0] = -1;
        int ans = 0;
        for(int i=1;i<n;i++)
        {
            int min = MAX, mini = -1;
    
            for(int j=0;j<n;j++)
            {
                if(d[j]!=-1 && d[j]<min)
                {
                    min = d[j];
                    mini = j;
                }
            }
            if(mini == -1)
                return -1;
            d[mini] = -1;
            if(f)
            {
                v[i].first = mini;
                v[i].second = fa[mini];
            }
            ans += min;
            for(int j=0;j<n;j++)
                if(d[j]!=-1 && d[j] > g[mini][j])
                {
                    fa[j] = mini;
                    d[j] = g[mini][j];
                }
        }
        return ans;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n, m;
            memset(g, 0x3f, sizeof(g));
            scanf("%d%d",&n, &m);
            int a, b, c;
            for(int i=0;i<m;i++)
            {
                scanf("%d%d%d", &a, &b, &c);
                g[a-1][b-1] = g[b-1][a-1] = c;
            }
            int ans = prim(n, m, 1);
            for(int i=1;i<n;i++)
            {
                int t = g[v[i].first][v[i].second];
                g[v[i].first][v[i].second]
                = g[v[i].second][v[i].first] = MAX;
                if(ans == prim(n, m, 0))
                {
                    ans = -1;
                    break;
                }
                g[v[i].first][v[i].second]
                = g[v[i].second][v[i].first] = t;
            }
            if(ans == -1)
                printf("Not Unique!\n");
            else
                printf("%d\n",ans);
        }
        return 0;
    }

     

    展开全文
  • 判断最小生成树唯一

    千次阅读 2016-12-13 19:38:51
    先用kruskal算法算出最小生成树,并把最小生成树的边记录下来。然后依次枚举删除边,用其他的边再次使用kruskal算法算出最小生成树。如果算出的代价和原来的相同,则不唯一,否则唯一。另外当我们删除一条边之后,...

    先用kruskal算法算出最小生成树,并把最小生成树的边记录下来。然后依次枚举删除边,用其他的边再次使用kruskal算法算出最小生成树。如果算出的代价和原来的相同,则不唯一,否则唯一。另外当我们删除一条边之后,可能根本构不成一颗生成树,要判断一下。

    代码如下:

    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <cmath>
    #include <queue>
    #include <new>
    #include <set>
    #include <map>
    
    using namespace std;
    
    const int maxn = 1000;
    int p[maxn], x[maxn], y[maxn], n;
    struct edge
    {
        int u, v, cost;
        bool operator < (const edge& b) const
        {
            return cost < b.cost;
        }
    };
    vector<edge> edges;
    vector<int> mst_edges;
    
    int find_root(int x)
    {
        if (p[x] == -1) return x;
        return p[x] = find_root(p[x]);
    }
    
    void kruskal()
    {
        memset(p, -1, sizeof(p));
        sort(edges.begin(), edges.end());
    
        mst_edges.clear();
        int cost = 0;
        for (int i = 0; i < edges.size(); i++)
        {
            int x = edges[i].u, y = edges[i].v;
            int rx = find_root(x);
            int ry = find_root(y);
            if (rx != ry)
            {
                p[rx] = ry;
                cost += edges[i].cost;
                mst_edges.push_back(i);
            }
        }
    
        printf("%d\n", cost);
    
        bool ok = false;
        for (int i = 0; i < mst_edges.size(); i++)
        {
            memset(p, -1, sizeof(p));
            int ans = 0, k = 0;
            for (int j = 0; j < edges.size(); j++)
            {
                if (mst_edges[i] == j) continue;
                int x = edges[j].u, y = edges[j].v;
                int rx = find_root(x);
                int ry = find_root(y);
                if (rx != ry)
                {
                    p[rx] = ry;
                    ans += edges[j].cost;
                    k++;
                }
            }
    
            if (ans == cost && k == n - 1)//新算出的生成树的代价和最小生成树代价相同,且能构成一棵树(最小生成树的边数肯定是n - 1)
            {
                ok = true;
                break;
            }
        }
    
        if (ok) printf("Yes\n");
        else printf("No\n");
    }
    
    int main()
    {
        //freopen("1.txt", "r", stdin);
        int T, Case = 0;
        scanf("%d", &T);
        while (T--)
        {
            scanf("%d", &n);
            edges.clear();
            for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
            for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            {
                int d = abs(x[i] - x[j]) + abs(y[i] - y[j]);
                edges.push_back(edge{i, j, d});
            }
    
            printf("case #%d:\n", Case++);
    
            kruskal();
        }
        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

    展开全文
  • 给定一个带权无向图,如果是连通图,则至少存在一棵最小生成树,有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重,并且判断其是否唯一。 输入格式: 首先第一行给出两个整数:无向图中顶点数N(≤500...
  • 利用Prim算法求最小生成树,选择最小边时进行判断:是否有两个或以上的未选择顶点到已选顶点集合的权值相等的,若有则最小生成树唯一。同时在松弛计算的时候也要 对刚加进的顶点进行权值是否相等的判断。 #...
  • 进阶实验6-3.6 最小生成树唯一性 (35分) 给定一个带权无向图,如果是连通图,则至少存在一棵最小生成树,有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重,并且判断其是否唯一。 输入格式: 首先第一...
  • 哪有什么传送门…. ...为了增加难度,我们还想知道,保留最小边集的方案是否唯一,也就是最小生成树的边是否唯一。如果唯一,输出最小长度;如果不唯一,输出“Not Unique!”。 Input 第一行输入T,表示有T组...
  • 给定一个带权无向图,如果是连通图,则至少存在一棵最小生成树,有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重,并且判断其是否唯一。 输入格式: 首先第一行给出两个整数:无向图中顶点数 N(≤500...
  • 次小生成树:由最小生成树换一条边de
  • 7-14 最小生成树唯一

    千次阅读 2018-03-20 22:05:48
    给定一个带权无向图,如果是连通图,则至少存在一棵最小生成树,有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重,并且判断其是否唯一。输入格式:首先第一行给出两个整数:无向图中顶点数 N(≤)...
  • 给定一无向图,判断最小生成树是否唯一。 思路 先求出最小生成树,记录结果,依次删除树中各边,再求最小生成树,看与最初结果是否相同,若相同则不唯一 代码// // main.cpp // demo // // Created by shiyi-mac ...
  • 对于最小生成树上任意两点,如果只能经过最小生成树上的边,路径都是唯一的。而次小生成树可以由一条非最小生成树上的边换取一条最小生成树的边而得到。所以在生成最小生成树的同时,记录最小生成树上任意两点路径中...
  • 先建成最小生成树 显然继续再添加任意一条边都会形成环 倘若新添的这条边与形成的环中除新添的边以外的最大的边长度相等 说明最小生成树唯一 枚举一下就好(求这条边减环中除它以外的最大值就可以求次小生成树)...
  • 题目链接:http://poj.org/problem?id=1679 1.如果最小生成树唯一,那么删除第一次
  • prim:判断“最小生成树是否唯一”可以理解为“最小生成树和次小生成树是否相等” 求次小生成树的步骤如下 1)先求出最小生成树T,在prim的同时,用一个矩阵maxx[u][v]记录在树中连接u-v的路径中权值最大的边.
  • 最小生成树的构造

    千次阅读 2019-11-06 16:13:18
    最小生成树 树也是图的一个特例 什么是生成树?...1、最小生成树形状不唯一,但最小生成树权是唯一的。且为所有生成树中最小的 2、最小生成树边数为顶点数减1 3、若无向连通图边数比顶点数少1,图...
  • 最短路径生成树与最小生成树

    千次阅读 2019-10-13 17:05:07
    最小生成树 这时候大家会发现,最短路径生成树不就是求完最短路之后,路径所构成的树吗,其实就是这样的。但是这里要明白一点,最短路径生树不唯一。我们举一个最简单的例子,如下图: 只选 2-3权值的边构成一颗最...
  • /* *题目大意: *给出一个连通无向图,判断它的最小生成树是否唯一; *如果唯一,输出生成树的大小,否则输出"Not ... *则说明最小生成树唯一,否则最小生成树一定是唯一的; * *次小生成树的求法详见http://blo
  • 题目大意 : 给出数据组数 t , 一个有 n 个顶点和 m 条边的图和每条边的权值,两个点之间最多只有一条边相连,判断最小生成树是否唯一,若唯一,则输出最小生成树的权值和,否则输出 Not Unique! 大致思路 : ...
  • 7-14 最小生成树唯一性(30 分) 给定一个带权无向图,如果是连通图,则至少存在一棵最小生成树,有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重,并且判断其是否唯一。 输入格式: 首先第...
  • 最小生成树:Prim算法

    万次阅读 多人点赞 2018-09-17 20:48:08
    讲构建最小生成树的算法前,先来回顾一下什么是生成树,什么是最小生成树?生成树是指:在一个连通图Graph中,包含Graph中所有n个顶点的极小连通子图,一定包含Graph中的n-1条边(如果小于n-1条边,生成树会不连通。...
  • 理解最小生成树与权值最小边无关

    千次阅读 2016-11-21 14:07:45
    理解最小生成树与权值最小边无关@(算法学习)驳斥:具有n个顶点的有向图G的最小生成树唯一,则其权值最小的边一定有多条。有两种最小生成树,但是实际上权值最小的边只有一条。更简洁的说,最小生成树与权值最小的...
  • 最小生成树

    千次阅读 2018-10-12 16:22:22
    最小生成树不是唯一的,它是树,因为无圈;是生成树,因为包含每一个顶点。有两种算法 1.Prim算法 是贪婪算法,分步进行,每一步,都把一个顶点当作根加入树中。在每个阶段,有一个已知顶点的集合,其余顶点未知,...
  • 最小生成树算法总结

    2018-08-02 10:46:02
    最小生成树则是树中权值之和最小的一颗生成树,最小生成树也可能不唯一最小生成树一般有两种算法,一种是prim算法,另一种是krukal算法。两种算法都是基于贪心思想,但两种算法并不完全相同。   Prim算法: 通过...

空空如也

空空如也

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

最小生成树唯一吗