可以肯定的是如果第一条边确定,那么这颗最小生成树的个边的权值就相应确定。
那么,对权值进行排序,挨个边进行枚举,从而确定最小值。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mm(a,b) memset(a,b,sizeof(a))
#define ACCELERATE (ios::sync_with_stdio(false),cin.tie(0))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define MAXNL 0x3fffffff
#define MAXN 0x3f3f3f3f
using namespace std;//#define debugstruct node{int u,v,w;
};bool cmp(const node& a,const node& b){return a.wint fa[105];int get_father(int i){return fa[i]=fa[i]==i?i:get_father(fa[i]);
}int main()
{#ifdef debugfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif // debugnode mmp[5005];int n,m;while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){for(int i=0;iscanf("%d%d%d",&mmp[i].u,&mmp[i].v,&mmp[i].w);}sort(mmp,mmp+m,cmp);int flag=0;int ans=MAXN;for(int i=0;i<=m-n+1;i++){for(int j=1;j<=n;j++) fa[j]=j;int cnt=0;for(int j=i;jint fx=get_father(mmp[j].u),fy=get_father(mmp[j].v);if(fx!=fy){cnt++;fa[fx]=fy;if(cnt==n-1){flag=1;ans=min(ans,mmp[j].w-mmp[i].w);break;}}}}if(flag) printf("%d
",ans);else printf("-1
");}return 0;
}










