题目类型 次小生成树
题目意思
给出 n 个点 m 条边问最小生成树是否唯一 (n <= 100)
解题方法
先用kruscal算法求出最小生成树和构成最小生成树的边 然后对于这棵最小生成树用 dfs 求出任两点间路径上最长的一条边是多少
然后枚举刚才后面没用过的边 (u, v) , 新的生成树的最小花费是
w(u,v) - maxlen[u][v] (即现在枚举的边的权值 - 最小生成树上u,v间路径上最长的一条边)
w(u,v) - maxlen[u][v] (即现在枚举的边的权值 - 最小生成树上u,v间路径上最长的一条边)
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 100+10; vector<int>E[maxn], W[maxn]; int fa[maxn]; int maxlen[maxn][maxn]; int nodepre[maxn], npre; struct Edge { int u, v, w; bool operator < (const Edge & rhs) const { return w < rhs.w; } }e[maxn*maxn]; int find(int x) { return fa[x] == x ? x : find(fa[x]); } void dfs(int u, int fa) { // nodepre 保存前面访问过的点,对于边(u,v)-> maxlen[pre][v] = max(maxlen[pre][v], W[u][i]); nodepre[npre++] = u; for( int i=0; i<E[u].size(); i++ ) { int v = E[u][i]; if(v == fa) continue; maxlen[u][v] = maxlen[v][u] = W[u][i]; for( int j=0; j<npre; j++ ) { int pre = nodepre[j]; maxlen[pre][v] = max(maxlen[pre][u], W[u][i]); maxlen[v][pre] = maxlen[pre][v]; } dfs(v, u); } } int main() { freopen("in", "r", stdin); int t; scanf("%d", &t); while(t--) { int n, m; scanf("%d%d", &n, &m); for( int i=0; i<m; i++ ) { scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); } sort(e, e + m); for( int i=1; i<=n; i++ ) E[i].clear(), W[i].clear(); for( int i=1; i<=n; i++ ) fa[i] = i; int tn = n, ti; int cost = 0; for( int i=0; i<m; i++ ) { // kruscal 算法 int u = e[i].u, v = e[i].v, w = e[i].w; int x = find(u); int y = find(v); if(x != y) { fa[x] = y; E[u].push_back(v); W[u].push_back(w); E[v].push_back(u); W[v].push_back(w); tn--; cost += w; if(tn == 1) { ti = i+1; break; } } } npre = 0; for( int i=1; i<=n; i++ ) for( int j=1; j<=n; j++ ) maxlen[i][j] = 0; dfs(1, -1); // 求最小生成树上任两个间路径最长的边 bool flag = true; for( int i=ti; i<m; i++ ) { // 枚举后面没用过的边 int u = e[i].u, v = e[i].v, w = e[i].w; if(cost == cost + w - maxlen[u][v]) { // 如果相等说明最小生成树不唯一 flag = false; break; } } if(flag) printf("%d\n", cost); else printf("Not Unique!\n"); } return 0; }