【Kruskal】Slim Span

[Uva1395]Slim Span

题目略……

试题分析：codevs1001舒适的路线上加一个判一下连通性就好，顺便把除改成减

代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read(){

    int x=0,f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

int N,M;

struct data{

    int x,y,v;

}e[5001];

bool cmp(data a,data b){

    return a.v<b.v;

}

int fa[5001];

void init(){

    for(int i=1;i<=N;i++) fa[i]=i;

    return ;

}

int find(int x){

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

    return x;

}

int ans1,ans2;

int main(){

    while(1){

        N=read(),M=read();

        if(!(N+M)) break;

        if(M==0){puts("-1");continue;}

        for(int i=1;i<=M;i++){

            e[i].x=read(),e[i].y=read();

            e[i].v=read();

        }

        ans1=ans2=-1;

        bool alflag=false;

        sort(e+1,e+M+1,cmp);

        for(int i=1;i<=M;i++){

            init();

            for(int j=i;j<=M;j++){

                int u=find(e[j].x),v=find(e[j].y);fa[v]=u;

                if(ans1!=-1&&e[j].v-e[i].v>=ans2-ans1) break;

                bool flag=false;

                for(int k=1;k<=N;k++) if(find(k)!=find(1)) {flag=true;break;}

                if(!flag){ans1=e[i].v;ans2=e[j].v;break;}

            }

            if(ans1==-1){puts("-1");alflag=true;break;}

        }

        if(!alflag)printf("%d\n",ans2-ans1);

    }

}