一道简单的图论题（并查集+Kruskal）
求一个图的的生成树，要求最大边减最小边之差最小，输出权值之差，如果没有，输出-1
要求权值差最小，所以首先将边按权值排序，枚举最小边，对于每个最小边从小到大枚举最大边
用并查集判断是否连通，如果可以生成树更新ans
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 using namespace std; 6 #define inf 0x7f7f7f7f 7 #define rep(i,n) for(int (i)=0;(i)<(n);i++) 8 #define ABS(x,y) (x-y>0)?(x-y):(y-x) 9 #define mem(a) memset(a,0,sizeof(a)); 10 #define in(a) cin>>a 11 #define out(a) cout<<a 12 const int maxn=110; 13 struct Edge 14 { 15 int u; 16 int v; 17 int w; 18 Edge(int u,int v,int w):u(u),v(v),w(w){} 19 }; 20 int n,m; int p[maxn]; 21 int cmp(const Edge& a,const Edge& b){ 22 return a.w<b.w; 23 } 24 int find(int x){ 25 return p[x]==x?x:p[x]=find(p[x]); 26 } 27 int main() 28 { //freopen("input.txt","r",stdin); 29 while(scanf("%d%d", &n, &m) == 2 && (n || m)){ 30 vector<Edge> e; int u,v,w; 31 for(int i=0;i<m;i++){ 32 scanf("%d%d%d", &u, &v, &w); 33 e.push_back(Edge(u,v,w)); 34 } 35 sort(e.begin(),e.end(),cmp); 36 int ans=inf; int sign=0; 37 for(int L=0;L<e.size();L++){ 38 for(int i=0;i<=n;i++) p[i]=i; 39 int cnt=0; int beg=e[L].w; 40 int end=beg; 41 for(int R=L;R<e.size();R++){ 42 int x=find(e[R].u);;int y=find(e[R].v); 43 if(x!=y){ 44 ++cnt; 45 p[x]=y; 46 end=max(end,e[R].w); 47 } 48 if(cnt==n-1) break; 49 } 50 if(cnt==n-1){ 51 sign=1; 52 ans=min(ans,end-beg); 53 } 54 } 55 if(sign==1) printf("%d ", ans); 56 else printf("-1 "); 57 } 58 return 0; 59 }