UVALive-3887 Slim Span （kruskal）

题目大意：定义无向图生成树的最大边与最小边的差为苗条度，找出苗条度最小的生成树的苗条度。

题目分析：先将所有边按权值从小到大排序，在连续区间[L,R]中的边如果能构成一棵生成树，那么这棵树一定有最小的苗条度。枚举所有这样的区间。

代码如下：

# include<iostream>

# include<cstdio>

# include<set>

# include<queue>

# include<cstring>

# include<algorithm>

using namespace std;

# define REP(i,s,n) for(int i=s;i<n;++i)

# define CL(a,b) memset(a,b,sizeof(a))

# define CLL(a,b,n) fill(a,a+n,b)

const int N=105;

const int INF=1<<30;

struct Edge

{

    int u,v,w;

    bool operator < (const Edge &a) const {

        return w<a.w;

    }

};

Edge e[5005];

int fa[N],n,m;

int findFa(int u)

{

    if(fa[u]!=u)

        return fa[u]=findFa(fa[u]);

    return u;

}

bool judge()

{

    int cnt=0;

    REP(i,1,n+1) if(fa[i]==i) ++cnt;

    return cnt==1;

}

int main()

{

    //freopen("UVALive-3887 Slim Span.txt","r",stdin);

    while(scanf("%d%d",&n,&m)&&(n+m))

    {

        REP(i,0,m) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

        sort(e,e+m);

        int ans=INF;

        REP(L,0,m){

            REP(i,1,n+1) fa[i]=i;

            REP(R,L,m){

                int u=e[R].u,v=e[R].v;

                int a=findFa(u);

                int b=findFa(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;

}