POJ-1679-The Unique MST（判断最小生成树是否唯一）-白红宇

POJ-1679-The Unique MST（判断最小生成树是否唯一）

阅读量：244 次

发布时间：2019-03-01

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

题意：给定n(<=100)个点，m条带权边。问最小生成树MST是否唯一。

题解：

判断依据——如果在选一个点加进来的时候，有两条及以上的路径可以选择，那么这个最小生成树就就是不唯一的。

图片说明：

AC代码:

ps(思路很简单，具体操作的时候注意一下)

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define int long long#define pb push_back#define dbg(x) cout << #x << ">>>" << x << endl;#define mst(a, x) memset(a, x, sizeof(a))using namespace std;const int maxn = 1e2 + 10;int n, m, u, v, w;int g[maxn][maxn];int vis[maxn], d[maxn];int ans, cnt[maxn];bool Unique_MST_prim() { bool f = true; for (int i = 1; i <= n; i++) vis[i] = cnt[i] = 0, d[i] = 9e18; //初始化 for (int i = 1; i <= n; i++) { int t = -1; for (int j = 1; j <= n; j++) { if (vis[j] == 0 && (t == -1 || d[j] < d[t])) t = j; } vis[t] = 1; //标记 if (cnt[t] > 1) f = false; //有多个选择到达点t if (i > 1) ans += d[t]; //第一个点不加，i==1是d[t]=1e9 for (int j = 1; j <= n; j++) { if (vis[j] || g[t][j] == 9e18) continue; if (d[j] == g[t][j]) cnt[j]++; if (d[j] > g[t][j]) d[j] = g[t][j], cnt[j] = 1; //恢复为只有一条路径到达点j } } return f;}void init() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = 9e18; for (int i = 1; i <= n; i++) g[i][i] = 0;}signed main() { int T; cin >> T; while (T--) { cin >> n >> m; init(); for (int i = 1; i <= m; i++) { cin >> u >> v >> w; g[u][v] = g[v][u] = w; } ans = 0; if (!Unique_MST_prim()) cout << "Not Unique!" << endl; else cout << ans << endl; } return 0;}