pku 3522 Slim Span(最小生成树变形）

题意：求一个无向图中所有的生成树的最大权值边与最小权值边的差值的最小值。

思路：Kruskal

设某棵生成树的最大权值边为maxWeight[i],最小权值边为minWeight[i].答案smallest = min(maxWeight[i] - minWeight[i]);

＝＝》求所有的生成树。

（1）对所有的边按权值从小到大进行排序。

（2）对[i, m - 1]条边求最小生成树，记录maxWeight, minWeight（0 <= i <= m - 1).如果不能组成生成树，则接下来的从[i + 1, m - 1] ,[i + 2, m - 1] .....也不可能有生成树了。

（3） smallest = min(maxWeight - minWeight)，即为所求;

源代码：

#include
#include
using namespace std;
const int INF = 999999999;
const int MaxNode = 100;
const int MaxEdge = MaxNode * MaxNode / 2;
struct Edge {
      int a, b, w;
      bool operator < (const Edge &e) const {
           return w < e.w;
      }
}edge[MaxEdge];
int p[MaxNode + 1], rank[MaxNode + 1];
void makeSet(int n) //并查集初始化
{
      for(int i = 1; i <= n; i ++) {
            p[i] = i;
            rank[i] = 0;
      }
}
int findSet(int x)//寻找结点X所在集合的根
{
      if(x != p[x])
            p[x] = findSet(p[x]);
      return p[x];
}
void unionSet(int x, int y)//合并两个集合
{
      if(rank[x] > rank[y]) {
            p[y] = x;
      }else {
            p[x] = y;
            if(rank[x] == rank[y]) ++ rank[x];
      }
}
int main()
{
      int n, m;
      while(scanf("%d %d", &n, &m) && (n || m)) {
            int i, a, b, w;
            for(i = 0; i < m; i ++) {
                  scanf("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].w); 
            }
            sort(edge, edge + m);//按照边权大小从小到大对边进行排序
            int smallest = INF;
            for(i = 0; i < m; i ++) {
                  makeSet(n);
                  int maxWeight = - INF;
                  int minWeight = INF;
                  int k = i, number = n - 1;
                  while(k < m && number) {
                        int fx = findSet(edge[k].a); //结点edge[k].a所在集合的根
                        int fy = findSet(edge[k].b); //结点edge[k].b所在集合的根
                        if(fx != fy) {//edge[i].a edge[i].b不在同一个集合中

 

                            number --;
                              maxWeight = max(maxWeight, edge[k].w);
                              minWeight = min(minWeight, edge[k].w);
                              unionSet(fx, fy); //合并以fx， fy为根的两个集合
                        }
                        k ++;
                  }
                  if(number) break; //从第i条边到最后一条边不能再连成一棵生成树，故退出
                  smallest = min(smallest, maxWeight - minWeight);
            }
            if(smallest == INF) printf("-1\n");//不能构成生成树
            else printf("%d\n", smallest);
      }
      return(0);
}