7-14 最小生成树的唯一性-白红宇

7-14 最小生成树的唯一性

阅读量：4113 次

发布时间：2019-05-25

本文共 1470 字，大约阅读时间需要 4 分钟。

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

输入格式：

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

输出格式：

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

输入样例 1：

5 71 2 65 1 12 3 43 4 34 1 72 4 24 5 5

输出样例 1：

11Yes

输入样例 2：

4 51 2 12 3 13 4 24 1 23 1 3

输出样例 2：

4No

输入样例 3：

5 51 2 12 3 13 4 24 1 23 1 3

输出样例 3：

No MST2

思路：我们可能先判断连通性，由于结点数比较少，可以通过dfs直接判断连通块的个数，对于最小生成树的唯一性，我们可以通过求出次小生成的权值，在于最小生成树的权值进行比较即可。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           using namespace std;const int maxn=550;int vis[maxn];const long long int inf=0x3f3f3f3f3f3f3f;int G[maxn][maxn];vector
           
             v[maxn];int fa[maxn];long long int dis[maxn];long long int pa[maxn][maxn];bool used[maxn][maxn];int n,m;void dfs(int x){ if(vis[x]) return ; vis[x]=1; for(int i=0; i
            
             G[idx][i]) { fa[i]=idx; dis[i]=G[idx][i]; } } } } return ans;}long long int second_tree(long long int t){ long long int ans=inf; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i!=j&&used[i][j]==0) ans=min(ans,t+G[i][j]-pa[i][j]); } } return ans;}int main(){ cin>>n>>m; memset(vis,0,sizeof(vis)); memset(G,inf,sizeof(G)); for(int i=0; i
             
              >x>>y>>d; G[x][y]=G[y][x]=d; v[x].push_back(y); v[y].push_back(x); } int cnt=0; for(int i=1; i<=n; i++) { if(vis[i]) continue; cnt++; dfs(i); } if(cnt>1) { cout<<"No MST"<

转载地址：http://sfgsi.baihongyu.com/

你可能感兴趣的文章