板子题，开始看错题了，bug找了一年，有点难受
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <map> #include <queue> using namespace std; const int maxn=100+10; const int inf=0x3f3f3f3f; int c[maxn]; int found(int x) { if(x==c[x]) return x; else return c[x]=found(c[x]); } void unit(int x,int y) { x=found(x); y=found(y); if(x==y) return; else c[x]=y; } bool same(int x,int y) { return found(x)==found(y); } struct note { int u,v,w; bool operator <(const note &p) const { return w<p.w; } }aa[maxn*maxn/2]; void init(int n) { for(int i=0;i<=n;i++) { c[i]=i; } } int n,m; int main() { while(~scanf("%d %d",&n,&m)&&(n+m)) { int ans=inf; for(int i=1;i<=m;i++) scanf("%d%d%d",&aa[i].u,&aa[i].v,&aa[i].w); sort(aa+1,aa+1+m); for(int i=1;i<=m-n+2;i++) { init(n); int cnt=0; int flag=0; int cha=0; int mini=inf; int maxi=-1; for(int j=i;j<=m;j++) { if(!same(aa[j].u,aa[j].v)) { unit(aa[j].u,aa[j].v); cnt++; maxi=max(maxi,aa[j].w); mini=min(mini,aa[j].w); } if(cnt==n-1) break; } } if(cnt!=n-1) flag=1; if(!flag) { ans=min(ans,maxi-mini); } } if(ans==inf) printf("-1\n"); else printf("%d\n",ans); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8328287.html
