众筹网站开发价格/建立一个网站的费用

题目链接：点我
题意简述

求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

并查集生成最小生成树，将边按从小到大排序，生成一个树更新一下答案

#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
int n;
int pa[maxn];int find(int x){if(x!=pa[x]){return pa[x]=find(pa[x]);}else{return x;}
}
struct Edge {int u, v, d;Edge(int u, int v, int d):u(u),v(v),d(d) {}bool operator < (const Edge& rhs) const {return d < rhs.d;}
};vector<Edge> e;int solve() {int m = e.size();sort(e.begin(), e.end());int ans = INF;for(int L = 0; L < m; L++) {for(int i = 1; i <= n; i++) pa[i] = i;int cnt = n; // number of setsfor(int R = L; R < m; R++) {int u = find(e[R].u), v = find(e[R].v);if(u != v) {pa[u] = v;if(--cnt == 1) { ans = min(ans, e[R].d-e[L].d); break; }}}}if(ans == INF) ans = -1;return ans;
}int main() {int m, u, v, d;while(scanf("%d%d", &n, &m) == 2 && n) {e.clear();for(int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &d);e.push_back(Edge(u, v, d));}printf("%d\n", solve());}return 0;
}