7-6 最小生成树的唯一性（35 分)(次小生成树)

分手后的思念是犯贱 2022-03-07 06:36 196阅读 0赞

### 题目描述： ###

给定一个带权无向图，如果是连通图，则至少存在一棵最小生成树，有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重，并且判断其是否唯一。

输入格式：  
首先第一行给出两个整数：无向图中顶点数 N（≤500）和边数 M。随后 M 行，每行给出一条边的两个端点和权重，格式为“顶点1 顶点2 权重”，其中顶点从 1 到N 编号，权重为正整数。题目保证最小生成树的总权重不会超过 2  
30  
 。

输出格式：  
如果存在最小生成树，首先在第一行输出其总权重，第二行输出“Yes”，如果此树唯一，否则输出“No”。如果树不存在，则首先在第一行输出“No MST”，第二行输出图的连通集个数。

输入样例 1：  
5 7  
1 2 6  
5 1 1  
2 3 4  
3 4 3  
4 1 7  
2 4 2  
4 5 5  
输出样例 1：  
11  
Yes  
输入样例 2：  
4 5  
1 2 1  
2 3 1  
3 4 2  
4 1 2  
3 1 3  
输出样例 2：  
4  
No  
输入样例 3：  
5 5  
1 2 1  
2 3 1  
3 4 2  
4 1 2  
3 1 3  
输出样例 3：  
No MST  
2

###### 分析： ######

本题，先求出最小生成树，然后在把次小生成树求出来进行比较。  
至于是不是能够成最小生成树，直接用一个并查集就可以得出结论了。  
所以，本题的关键在于求次小生成树了。  
一开始我使用暴力枚举将最小生成树上的边依次删除，然后再求最小生成树，看两次的值是否相同。但是不幸的是超时了。  
贴上一组数据超时代码：

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    #define INF 1000000
    int Graph[501][501];
    int N,M;
    int MARK=1;
    int sum=0;
    int MMM=1;
    vector<int>Q[501];//保存最小生成树的边 
    int Find(int f[],int x)
    {
        if(f[x]==x)
            return x;
        return f[x]=Find(f,f[x]);
    }
    //flat的目的是为了区分是第一次求最小生成树，还是求次小生成树
    void Creat(int Graph[][501],int flat)
    {
        int weight[501];
        int vis[501];
        int p[501];
        int i,j,k;
        for(int i=1; i<=N; i++)
        {
            weight[i]=Graph[1][i];
            p[i]=1;
            vis[i]=0;
        }
        vis[1]=1;
        for(i=1; i<N; i++)
        {
            k=-1;
            j=1;
            int minx=INF;
            while(j<=N)
            {
                if(weight[j]&&minx>weight[j])
                {
                    k=j;
                    minx=weight[j];
                }
                j++;
            }
            if(k==-1)
            {
                MMM=0;
                sum=INF;
                break;
            }
            sum+=weight[k];
            weight[k]=0;
            if(flat)
            {
                Q[p[k]].push_back(k);//将p[k]到k这条边记录在vector中
            }
            for(j=1; j<=N; j++)
            {
                if(weight[j]&&weight[j]>Graph[k][j])
                {
                    weight[j]=Graph[k][j];
                    p[j]=k;
                }
            }
        }
    }
    int main()
    {
        int f[501];
        for(int i=1; i<501; i++)
            f[i]=i;
        scanf("%d%d",&N,&M);
        for(int i=0; i<=N; i++)
            for(int j=0; j<=N; j++)
                if(i==j)
                    Graph[i][j]=0;
                else
                    Graph[i][j]=INF;
        for(int i=0; i<M; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            int n=Find(f,a);
            int m=Find(f,b);
            if(n!=m)
                f[n]=m;
            if(Graph[a][b]>c)
            {
                Graph[a][b]=c;
                Graph[b][a]=c;
            }
        }
        Creat(Graph,1);//注意这里的1
        int mmm=MMM;
        int cnt=0;
        int minx=sum;
        for(int i=1; i<=N; i++)
        {
            for(int j=0; j<Q[i].size(); j++)//枚举把最小生成树中的边一次删除
            {
                    sum=0;
                    int y=Q[i][j];
                    int x=Graph[i][y];
                    Graph[i][y]=INF;//删除，即赋值为INF
                    Graph[y][i]=INF;
                    Creat(Graph,0);//注意这里的0
                    if(sum==minx)
                        cnt=1;
                    Graph[i][y]=x;//需要回溯 
                    Graph[y][i]=x;
    
            }
        }
        if(mmm==1)
        {
            printf("%d\n",minx);
            if(cnt==0)
                printf("Yes\n");
            else
                printf("No\n");
        }
        else
        {
            printf("No MST\n");
            int cnt=0;
            for(int i=1; i<=N; i++)
                if(f[i]==i)
                    cnt++;
            printf("%d\n",cnt);
        }
    }

上述思想比较简单。但是复杂度太高。  
次小生成树参考博客：[https://blog.csdn.net/stay\_accept/article/details/50960185][https_blog.csdn.net_stay_accept_article_details_50960185]

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    #define INF 1000000
    int Graph[501][501];
    int N,M;
    int MARK=1;
    int sum=0;
    int MMM=1;
    vector<int>Q[501];
    int used[501][501]={0};
    int path[501][501];
    int Find(int f[],int x)
    {
        if(f[x]==x)
            return x;
        return f[x]=Find(f,f[x]);
    }
    void Creat(int Graph[][501])
    {
        int weight[501];
        int vis[501];
        int p[501];
        int i,j,k;
        for(int i=1; i<=N; i++)
        {
            weight[i]=Graph[1][i];
            vis[i]=0;
            p[i]=1;
        }
        vis[1]=1;
        for(i=1; i<N; i++)
        {
            k=-1;
            j=1;
            int minx=INF;
            while(j<=N)
            {
                if(vis[j]==0&&minx>weight[j])
                {
                    k=j;
                    minx=weight[j];
                }
                j++;
            }
            if(k==-1)
            {
                MMM=0;
                sum=INF;
                break;
            }
            sum+=weight[k];
            vis[k]=1;
            used[p[k]][k]=1;//如果是最小生成树上的边则标记一下
            used[k][p[k]]=1;
            for(j=1; j<=N; j++)
            {
                if(j!=k&&vis[j])//求出j到k这个环路上值最大的边
                {
                    path[j][k]=path[k][j]=max(path[j][k],weight[k]);
                }
                if(vis[j]==0&&weight[j]>Graph[k][j])
                {
                    weight[j]=Graph[k][j];
                    p[j]=k;
                }
            }
        }
    }
    int ans=INF;
    void SecondTree(int Graph[][501])//求次小生成树的函数
    {
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=N;j++)
            {
                if(i!=j&&used[i][j]==0)//将不是最小生成树上的边加入进去，并删除环路上最大的边
                {
                    ans=min(ans,sum+Graph[i][j]-path[i][j]);
                }
            }
        }
    }
    int main()
    {
        int f[501];
        for(int i=1; i<501; i++)
            f[i]=i;
        scanf("%d%d",&N,&M);
        for(int i=0; i<=N; i++)
            for(int j=0; j<=N; j++)
                if(i==j)
                    Graph[i][j]=0;
                else
                    Graph[i][j]=INF;
        for(int i=0; i<M; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            int n=Find(f,a);
            int m=Find(f,b);
            if(n!=m)
                f[n]=m;
            if(Graph[a][b]>c)
            {
                Graph[a][b]=c;
                Graph[b][a]=c;
            }
        }
        Creat(Graph);
        int mmm=MMM;
        int cnt=0;
        int minx=sum;
        SecondTree(Graph);
        if(ans==sum)
            cnt=1;
        if(mmm==1)
        {
            printf("%d\n",minx);
            if(cnt==0)
                printf("Yes\n");
            else
                printf("No\n");
        }
        else
        {
            printf("No MST\n");
            int cnt=0;
            for(int i=1; i<=N; i++)
                if(f[i]==i)
                    cnt++;
            printf("%d\n",cnt);
        }
    }

[https_blog.csdn.net_stay_accept_article_details_50960185]: https://blog.csdn.net/stay_accept/article/details/50960185