求最小生成树的最大边与最小边之差最小 利用kruskal
#include <iostream> #include <algorithm> using namespace std; int n,m,parent[20000]; struct node { int x,y,w; }tree[20000]; int cmp(node aa,node bb) { return aa.w<bb.w; } void makeset() { int x; for(x=1;x<=n;x++) parent[x]=x; } int findset(int x) { if(x!=parent[x]) parent[x]=findset(parent[x]); return parent[x]; } void unionset(int x,int y) { x=findset(x); y=findset(y); if(parent[x]==parent[y]) return ; parent[y]=x; } int kruskal() { int i,j,cnt=0,mini,maxn=9999999999,minc=999999999,flg=0,f; sort(tree,tree+m,cmp); for(j=0;j<m;j++) { makeset(); cnt=0; for(i=j;i<m;i++) { f=0; if(findset(tree[i].x)!=findset(tree[i].y)) { cnt++; unionset(tree[i].x,tree[i].y); if(cnt==1) mini=tree[i].w; if(cnt==n-1) { flg=1; f=1; maxn=tree[i].w; break; } } } if(f && maxn-mini<minc) minc=maxn-mini; } if(flg==0) return -1; else return minc; } int main() { int i,j,minc=999999999; while(scanf("%d%d",&n,&m)!=EOF) { if(!n && !m) break; for(i=0;i<m;i++) scanf("%d%d%d",&tree[i].x,&tree[i].y,&tree[i].w); printf("%d/n",kruskal()); } return 0; }