UVA 1395 & LALive 3887 Slim Span --- kruskal

题目链接 https://vjudge.net/problem/UVA-1395

参考https://www.cnblogs.com/20143605--pcx/p/4927478.html

 这道题是求【苗条生成树】，要求生成树最大边和最小边差值最小

kruskal算法里面，将边按权值从小到大排序，最小的边e1加入后，相当于是一种贪心的思想，后面的边能要则要，这样就能让最大边权值尽量的小，然后可以不要最小边e1，从e2开始用同样方法找出最小差值，循环此过程

    #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 110;const int INF = 2e10;struct Edge {int u,v,w;bool operator < (const Edge &a) const {return w < a.w;}} e[10000];int fa[N], n, m;int Find(int u) {if(fa[u] == u) return u;return fa[u] = Find(fa[u]);}bool judge() {int cnt = 0;for(int i = 1;i <= n;i++) {if(fa[i] == i) cnt++;}return cnt == 1;}int main() {while(scanf("%d%d",&n,&m) != EOF && (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);int ans = INF;for(int l = 0;l < m;l++) {for(int i = 1;i <= n;i++) fa[i] = i;for(int r = l;r < m;r++) {int u = e[r].u;int v = e[r].v;int a = Find(u);int b = Find(v);if(a!=b) {fa[a] = b;}if(judge()) {ans = min(ans, e[r].w-e[l].w);break;}}}if(ans == INF) {printf("-1\n");} else {printf("%d\n",ans);}}return 0;}