求一张图所有生成树中的最大边与最小边差的最小值

题目来源：常州曹文夏令营
题意：
输入一个N个点，M条边的无向图（可能有重边），输出在它所有的生成树中，最大边与最小边的差值的最小值。如果图不联通，输出-1.
输入格式：
第一行,两个用空格隔开的整数 N 和 M,分别表示顶点数和边数。
下面 M 行,每行 3 个数 u,v,w,表示 u 和 v 之间有一条权值为 w 的无向边。
数据范围：
N<=100,M<=3000,w<=10000

用搜索计算出有100个点的图的每个一生成树显然是会超时的。注意到题目只要求输出差值的最小值，可以想到用二分答案解决这个问题。

代码如下：

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 102
#define MAXM 3003

typedef struct edge
{
   int u,v,w;
}edge;

int N,M;
int fa[MAXN];
int first[10000];
edge e[MAXM];

int ecmp(const void *a,const void *b)
{
   if(((edge *)a)->w > ((edge *)b)->w)    return 1;
   return -1;
}

void init()
{
   int i;
   scanf("%d%d\n",&N,&M);
   for(i = 0;i < M;i ++)
       scanf("%d%d%d\n",&e[i].u,&e[i].v,&e[i].w);
   qsort(e,M,sizeof(edge),ecmp);
   for(i = M - 1;i >= 0;i --)
       first[e[i].w] = i;
}

inline void init_union()
{
   int i;
   for(i = 1;i <= N;i ++)
       fa[i] = i;
}

int getfa(int x)
{
   if(fa[x] != x)
       fa[x] = getfa(fa[x]);
   return fa[x];
}

inline int allconnect()   //判断图是否联通
{
   int i,x;
   x = getfa(1);
   for(i = 2;i <= N;i ++)
       if(getfa(i) != x)    return 0;
   return 1;
}

int check(int diff)
{
   int i,j,x,y;
   for(i = 0;i < M;i ++)  //枚举起点
       if(first[e[i].w] == i)
       {
           init_union();
           for(j = i;e[j].w - e[i].w <= diff && j < M;j ++)
           {
               x = getfa(e[j].u);
               y = getfa(e[j].v);
               fa[x] = y;
           }
           if(allconnect())    return 1;
       }
   return 0;
}

void solve()
{
   int mid;
   int l,r;
   l = 0;
   r = e[M - 1].w - e[0].w;
   while(l < r)
   {
       mid = (l + r) / 2;
       //printf("%d\n",mid);
       if(check(mid))    r = mid;
       else    l = mid + 1;
   }
   printf("%d\n",l);
}

void check_graph()
{
   int i,x,y;
   init_union();
   for(i = 0;i < M;i ++)
   {
       x = getfa(e[i].u);
       y = getfa(e[i].v);
       fa[x] = y;
   }
   if(allconnect() == 0)
   {
       printf("-1\n");
       fclose(stdout);
       exit(0);
   }
}

int main()
{
   freopen("span.in","r",stdin);
   freopen("span.out","w",stdout);
   init();
   check_graph();   //检查图是否联通
   solve();   //二分求解
   fclose(stdout);
   return 0;
}

其实，还有一个更简洁的方法：把所有边排序，枚举i，对i~M-1这M条边做一次Kruskal。那么，结果就是每一次Kruskal求得的最小生成树的最大边和最小边的差值的最小值。

C语言: 高亮代码由发芽网提供

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

const int MaxN=111;
int N,M,fa[MaxN];
struct node
{
   int x,y,len;
} e[MaxN*MaxN];


bool cmp(node a, node b)
{
   return a.len<b.len;
}

int getfather(int x)
{
   if (x==fa[x]) return x;
   else
   {
       fa[x]=getfather(fa[x]);
       return fa[x];
   }
}

int kruscal(int sta)
{
   for (int i=1; i<=N; ++i) fa[i]=i;
   int set_num=N;
   if (N<=1) return 0;
   for (int i=sta; i<=M; ++i)
   {
       int t1=getfather(e[i].x);
       int t2=getfather(e[i].y);
       if (t1!=t2)
       {
           --set_num;
           fa[t1]=t2;
           if (set_num==1) return e[i].len-e[sta].len;
       }
   }
   return 111111111;
}

         

int main()
{
   freopen("span.in","r",stdin);
   freopen("span.out","w",stdout);
   scanf("%d %d",&N,&M);
   int ans=111111111;
   for (int i=1; i<=M; ++i) scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].len);
   sort(e+1,e+M+1,cmp);
   for (int i=1; i<=M; ++i)   //枚举起始边
         ans=min(ans,kruscal(i));
   if (ans==111111111) printf("-1\n");   //图不联通
   else printf("%d\n",ans);

   return 0;

}

第二个算法是建立在对Kruskal算法的深入理解上的。Kruskal是一个贪心算法，它加入的边的权值一定是不递减的。因此，若给定了起始边，Kruskal获得的生成树的最大边和最小边的差值一定是最小的。