題目鏈接 https://vjudge.net/problem/POJ-1679

Given a connected undirected graph, tell if its minimum spanning tree is unique.

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V’, E’), with the following properties:
1. V’ = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E’) of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E’.
Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string ‘Not Unique!’.
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!

【題意】
給定一張無向圖，判斷這個圖的最小生成樹是否唯一，如果唯一則輸出最小生成樹的權值，否則輸出 “Not Unique!”

【思路】
題目實際上想問的是次小生成樹的權值，如果次小生成樹的權值和最小生成樹一樣，那么最小生成樹不唯一。最小生成樹可以在求出每對點之間的最小瓶頸路后枚舉剩下的邊求出。具體做法是先求最小生成樹，同時用dfs求出任意兩點的最小瓶頸路，然后枚舉所有不在最小生成樹中的邊，假設這條邊的端點是u和v，用這條邊去替換原來最小生成樹中u,v的最小瓶頸路，迭代取最小值。所以次小生成樹就是最小瓶頸路的一個簡單應用。

#include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std;const int inf = 0x3f3f3f3f; const int maxn = 105; const int maxm = 10050;struct Edge {int from, to, dist;Edge(int f = 0, int t = 0, int d = 0) :from(f), to(t), dist(d) {}bool operator<(const Edge& e) const {return dist < e.dist;} };int n, m; int par[maxn]; bool used[maxn];//dfs的訪問標記數組 bool vis[maxm];//某條邊是否使用過 int f[maxn][maxn]; vector<Edge> edges, g[maxn];int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }int kruscal() {int cnt = 0, ans = 0;for (int i = 0; i < n; ++i) {par[i] = i;g[i].clear();}for (int i = 0; i < m; ++i) {int u = edges[i].from;int v = edges[i].to;int x = find(u);int y = find(v);if (x != y) {par[x] = y;ans += edges[i].dist;vis[i] = true;g[u].push_back(Edge(u, v, edges[i].dist));g[v].push_back(Edge(v, u, edges[i].dist));if (++cnt == n - 1) break;}}return ans; }void dfs(int u) {used[u] = 1;for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].to;if (!used[v]) {for (int x = 0; x < n; ++x) {if (used[x]) f[x][v] = f[v][x] = max(f[x][u], g[u][i].dist);}dfs(v);}} }int main() {int t;scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);edges.clear();memset(vis, 0, sizeof(vis));for (int i = 0; i < m; ++i) {int u, v, c;scanf("%d%d%d", &u, &v, &c);--u, --v;edges.push_back(Edge(u, v, c));}sort(edges.begin(), edges.end());int mst = kruscal();memset(used, 0, sizeof(used));memset(f, 0, sizeof(f));dfs(0);int ans = inf;//枚舉所有沒有用過的邊for (int i = 0; i < m; ++i) {if (!vis[i]) { ans = min(ans, mst - f[edges[i].from][edges[i].to] + edges[i].dist);}}if (ans == mst) printf("Not Unique!\n");else printf("%d\n", mst);}return 0; }

轉載于:https://www.cnblogs.com/wafish/p/10465403.html

總結

以上是生活随笔為你收集整理的POJ 1679 - The Unique MST（次小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。