题意:判断最小生成树是否唯一 求出次小生成树比较
思路:慢一点的方法就是求出最小生成树 每次去掉最小生成树的一条边再求最小生成树 比较慢
更好的方法是 求出最小生成树后加上一条没有用到的边 然后必定出现一条回路 去掉回路上权值最大的边 做m-(n-1)次
求一次最小生成树 然后n^2的时间预处理最小生成树上两点之间最大的边权 最后换边 MST-加进去的边的权值-回路上的最大边权值 取小
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 110; struct edge { int u, v, w; edge(){} edge(int u, int v, int w): u(u), v(v), w(w){} }a[100000]; int f[maxn]; int dp[maxn][maxn]; int n, m; bool ok[100000]; vector <edge> G[maxn]; bool cmp(edge a, edge b) { return a.w < b.w; } int find(int x) { if(x != f[x]) return f[x] = find(f[x]); return f[x]; } int MST() { for(int i = 1; i <= n; i++) { f[i] = i; G[i].clear(); } memset(ok, false, sizeof(ok)); sort(a, a+m, cmp); memset(dp, 0, sizeof(dp)); int sum = 0; for(int i = 0; i < m; i++) { int u = a[i].u; int v = a[i].v; int w = a[i].w; int x = find(u); int y = find(v); if(x != y) { sum += w; f[x] = y; G[u].push_back(edge(u, v, w)); G[v].push_back(edge(v, u, w)); ok[i] = true; } } return sum; } void BFS(int x) { queue <edge> Q; Q.push(edge(-1, x, 0)); while(!Q.empty()) { edge u = Q.front(); Q.pop(); for(int i = 0; i < G[u.v].size(); i++) { edge v = G[u.v][i]; if(v.v == u.u) continue; int temp = max(u.w, v.w); dp[x][v.v] = dp[v.v][x] = max(dp[x][v.v], temp); Q.push(edge(v.u, v.v, temp)); } } } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) scanf("%d %d %d", &a[i].u, &a[i].v, &a[i].w); int ans = MST(); int sum = 999999999; for(int i = 1; i <= n; i++) BFS(i); for(int i = 0; i < m; i++) { if(ok[i]) continue; int u = a[i].u; int v = a[i].v; int w = a[i].w; sum = min(sum, ans+w-dp[u][v]); } if(ans == sum) puts("Not Unique!"); else printf("%d\n", ans); } return 0; }
POJ 1679 The Unique MST 次小生成树,布布扣,bubuko.com
原文:http://blog.csdn.net/u011686226/article/details/27957715