【kruscal】【最小生成树】poj3522 Slim Span

求一个生成树，使得最大边权和最小边权之差最小。由于数据太小，暴力枚举下界，求出相应的上界。最后取min即可。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n,m,fa[],rank[];

 void clear(){for(int i=;i<=n;i++) fa[i]=i; memset(rank,,sizeof(rank));}

 int findroot(int x)

 {

     if(fa[x]==x) return x;

     int rt=findroot(fa[x]);

     fa[x]=rt;

     return rt;

 }

 void Union(int U,int V)

 {

     if(rank[U]<rank[V]) fa[U]=V;

     else

       {

         fa[V]=U;

         if(rank[U]==rank[V]) rank[U]++;

       }

 }

 struct Edge{int u,v,w;};

 bool cmp(const Edge &a,const Edge &b){return a.w<b.w;}

 Edge edges[];

 int tot,ans,maxv;

 int main()

 {

     while()

       {

           scanf("%d%d",&n,&m);

           if(!n) break;

           for(int i=;i<=m;i++) scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);

           sort(edges+,edges+m+,cmp); ans=;

           for(int j=;j<=m;j++)

             {

                 tot=; clear();

                 for(int i=j;i<=m;i++)

                 {

                     int f1=findroot(edges[i].u),f2=findroot(edges[i].v);

                     if(f1!=f2) {Union(f1,f2); tot++; if(tot==n-) {maxv=edges[i].w; goto WIN;}}

                 }

               continue;

               WIN:ans=min(ans,maxv-edges[j].w);

             }

           printf("%d\n",ans!= ? ans : -);

       }

     return ;

 }