henrytb 的博客

henrytb 的博客

题解 UVA1395 【苗条的生成树 Slim Span】

posted on 2019-04-07 11:42:50 | under 题解 |

刘汝佳大法好!

我henrytb又来宣传刘汝佳紫书大法了QAQ

这道题类似最小生成树,只不过是让最大边权减最小边权最小

采用Kruskal求解最小生成树,只不过我们只是对于每一个边都从它开始Kruskal一遍,来算全所有情况。

每一遍都更新一下答案

code:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct edge{
    int a,b,w;
}e[100005];
int n,m,a[100005],b[100005],w[100005],fa[100005],ans,maxed;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
bool cmp(edge a,edge b){
    return a.w<b.w;
}
bool merg(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return 0;
    else fa[y]=x;
    return 1;
}
void init(){
    ans=2147483647;
    rep(i,1,n)fa[i]=i;
    sort(e+1,e+m+1,cmp);
}
bool kruskal(int ed){
    int now=0;
    rep(i,1,n)fa[i]=i;
    maxed=-1;
    rep(i,ed,m){
        if(merg(e[i].a,e[i].b)){
            maxed=e[i].w;
            if(++now==n-1)return true;
        }
    }
    return false;
}
int main(){
    while(~ scanf("%d%d",&n,&m)&&n){
        rep(i,1,m) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
        init();
        rep(i,1,m){
            if(kruskal(i)){
                ans=min(ans,maxed-e[i].w);
            }
        }
        printf("%d\n",ans==2147483647?-1:ans);
    }
    return 0;
}