本文主要是介绍Slim Span （UVA - 1395，最小生成树 + 简单应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
UVA-1395
二.题目大意：
给定 n 个点，m 条边的无向图.
定义生成树的 “苗条度” == max树边权值 - min树边权值.
求生成树的最小苗条度.
三.分析：
大体思路就是用 Kruskal 算法求解最小生成树.
由于生成树的 “苗条度” == max树边权值 - min树边权值
所以先 sort 一遍边的权值
然后从小到大枚举生成树的最小权值边
注意：用 cnt 来验证是否能构成生成树.
四.代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;const int M = 210;
const int inf = 0x3f3f3f3f;
struct node
{int u;int v;int w;
} edge[M * M];
int fa[M];void init(int n)
{for(int i = 1; i <= n; ++i)fa[i] = i;
}bool cmp(node a, node b)
{return a.w < b.w;
}int tofind(int x)
{if(x != fa[x])x = tofind(fa[x]);return fa[x];
}bool tojoin(int u, int v)
{int fu = tofind(u);int fv = tofind(v);if(fu != fv){fa[fu] = fv;return 1;}return 0;
}int main()
{int n, m;while(~scanf("%d %d", &n, &m)){if(n + m == 0)break;for(int i = 0; i < m; ++i)scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);sort(edge, edge + m, cmp);int ans = inf;///记录 “苗条度”for(int i = 0; i < m; ++i)///枚举生成树的最小权值边{init(n);int cnt = n - 1;int Min = edge[i].w;int Max = -inf;for(int j = i; j < m; ++j){if(tojoin(edge[j].u, edge[j].v)){Max = max(Max, edge[j].w);cnt--;}}if(!cnt)///构成生成树肯定需要 n - 1 条边ans = min(ans, Max - Min);}if(ans != inf)printf("%d\n", ans);elseprintf("-1\n");}return 0;
}
这篇关于Slim Span （UVA - 1395，最小生成树 + 简单应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
