题意：
给你一个图，让你求这个图中所有生成树中满足题目条件的，这个条件是生成树中最长边与最短边的差值最小。
思路：
根据最小瓶颈生成树的定义：在一个有权值的无向图中，求一个生成树最大边的权值尽量小。首先以K算法做这道题，先给所有边排好序，然后我可以从小到大枚举每一条边作为我所求生成树的最短边（即第一次以最短边求最小生成树，第二次删除第一条边，以第二条边为最短边求最小生成树，第三次删除第一条边和第二条边，以第三边为最短边求最小生成树。）然后在这个过程中更新 MST（maxE- minE）就好了。这么做的原因是：因为最小生成树一定是无向图的瓶颈生成树。即如果最短边（第一条边）已经定下来，那么最小生成树的 (maxE- minE)一定比其他以这个边为最短边的生成树的（maxE - min E）小。所以就可以依次枚举这个最短边，更新答案就好了。
代码：
1 import java.util.Scanner; 2 import java.util.Comparator; 3 import java.util.Arrays; 4 5 class Node{ 6 public int u, v, w, mark; 7 } 8 //结构排序 9 class mycmp implements Comparator {10 public int compare(Node A, Node B){ 11 return A.w - B.w; 12 } 13 }14 public class Main {15 final static int MAXN = 10000 + 13;16 final static int INF = 0x3f3f3f3f;17 static int[] pre = new int[MAXN];18 static Node[] map = new Node[MAXN];19 public static void main(String[] args){20 Scanner sc = new Scanner(System.in);21 while(true){22 int N,M;23 N = sc.nextInt();24 M = sc.nextInt();25 if(N == 0 && M == 0)break;26 for(int i = 1; i <= M; i++){27 map[i]=new Node(); 28 map[i].u = sc.nextInt();29 map[i].v = sc.nextInt();30 map[i].w = sc.nextInt();31 map[i].mark = 0;32 }33 met(N);34 Arrays.sort(map, 1, M + 1, new mycmp());35 int sst = ksu(N, M, 0); //SST 初始化为最小生成树的值36 for(int i = 1; i <= M; i++){ //求SST37 met(N);38 int temp = ksu(N, M, i);//以第 i + 1 条边作为第一条边（即删除前i条边后）求MST，如果不等于 -1 说明构造成功39 if(temp < sst && temp != -1){ 40 sst = temp;41 }42 }43 System.out.println(sst);44 }45 sc.close();46 }47 public static int ksu(int N, int M,int mark){ //删除 前 mark 条边 求 MST48 int cnt= 0;49 int st, ed;50 st = ed = map[1].w;51 boolean flag = true;52 for(int i = mark + 1; i <= M; i++){53 int fu = Find(map[i].u);54 int fv = Find(map[i].v);55 if(fu != fv){56 if(flag){57 st = map[i].w;58 flag = false;59 }60 cnt++;61 pre[fv] = fu;62 }63 if(cnt == N - 1){64 ed = map[i].w;65 return ed - st;66 }67 }68 return -1;69 }70 public static int Find(int x){71 return x == pre[x] ? x : (pre[x] = Find(pre[x]));72 }73 public static void debug(int M){74 for(int i = 1; i <= M; i++){75 System.out.println(i + " " + map[i].u + " " + map[i].v + " " + map [i].w + " "+ map[i].mark);76 }77 }78 public static void met(int N){79 for(int i = 1; i <= N; i++){80 pre[i] = i;81 }82 }83 }