Uva(1395)(Slim Span)

链接：https://vjudge.net/problem/UVA-1395
思路：表面看起来跟最小生成树没什么关系，其实不然，由于点比较少，可以用kruskal之前枚举边的起点，然后贪心取就可以得到当前枚举的最大边和最小边差值的最小，然后更新值即可，一开始我既枚举了起点又枚举了终点，完全没必要，浪费了一个n的复杂度被T了，后来发现完全是浪费改掉之后就A了
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 110;
int n,m;

struct edge{
    int from,to,dist;
    edge(){}
    edge(int f,int t,int d):from(f),to(t),dist(d){}
    bool operator<(const edge &r)const{
        return dist<r.dist;
    }
};

struct Kruskal{
    vector<int> G[maxn];
    int m,n;
    int par[maxn];
    vector<edge> edges;
    int done;

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
        for(int i=0;i<n;i++)par[i] = i;
    }

    void addedge(int from,int to,int dist){
        edges.push_back(edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);
        done = 0;
    }

    int getroot(int a){
        if(par[a]==a)return a;
        par[a] = getroot(par[a]);
        return par[a];
    }

    void merge(int a,int b){
        int p1 = getroot(a);
        int p2 = getroot(b);
        if(p1==p2)return;
        par[p2] = p1;
    }
    
    int kruskal(){
        int res = 1e9;
    sort(edges.begin(),edges.end());
    for(int k=0;k<edges.size();k++){//枚举起点
            done = 0;
            for(int p=0;p<n;p++)par[p] = p;
                int i;
    for(i=k;i<edges.size();i++){
        if(getroot(edges[i].from)!=getroot(edges[i].to)){
            merge(edges[i].from,edges[i].to);
            ++done;
        }
        if(done==n-1)break;
    }
if(done==n-1)res = min(res,edges[i].dist-edges[k].dist);//更新
}
return res;
}
}solver;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&m)&&(n+m)){
        solver.init(n);
        for(int i=0;i<m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a--;
            b--;
            solver.addedge(a,b,c);
            solver.addedge(b,a,c);
        }
        int res = solver.kruskal();
        printf("%d\n",res==1e9?-1:res);
    }
    return 0;
}