POJ 3552

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int VM=110; const int INF=999999999; struct Edge{ int u,v; int cap; }edge[VM*VM]; int n,m,ans,father[VM]; void makeSet(){ for(int i=1;i<=n;i++){ father[i]=i; } } int findSet(int x){ if(x!=father[x]){ father[x]=findSet(father[x]); } return father[x]; } int cmp(Edge a,Edge b){ return a.cap<b.cap; } void Kruskal(){ sort(edge,edge+m,cmp); for(int i=0;i<m;i++){ makeSet(); int cnt=0,tmp=INF; for(int j=i;j<m;j++){ int fx=findSet(edge[j].u); int fy=findSet(edge[j].v); if(fx!=fy){ father[fy]=fx; cnt++; if(cnt==n-1){ tmp=edge[j].cap-edge[i].cap; break; } } } if(tmp<ans) ans=tmp; } } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ if(n==0 && m==0) break; for(int i=0;i<m;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cap); ans=INF; Kruskal(); if(ans!=INF) printf("%d\n",ans); else printf("-1\n"); } return 0; }