UVA1395 Slim Span(最小生成树)
*原题链接*(洛谷)
非常水的一道题。看见让求最小边权差值的生成树，很容易想到kruskal。
一个暴力的想法是以每条边为最小边跑一遍kruskal，然后统计答案。时间复杂度，再看题中很小的数据范围和3s的时限。最后还真就过了。
不过我天真的想了一下二分最大差值，最后使时间复杂度成功升到。但最后还是过了。。
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,fa[N];
struct node{int from,to,w;
}edge[N];
bool cmp(node a,node b){return a.w<b.w;
}int find(int x){if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}bool check(int k){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++) fa[j]=j;int mn=edge[i].w,cnt=0;for(int j=i;j<=m;j++){if(edge[j].w-mn>k) break;int x=find(edge[j].from),y=find(edge[j].to);if(x==y) continue;cnt++,fa[x]=y;if(cnt==n-1) return true;}}return false;
}int main(){while(1){n=read(),m=read();if(!n&&!m) break;for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();edge[i]={x,y,w};}sort(edge+1,edge+1+m,cmp);int l=0,r=10000,ans=-1;//我太蠢了，其实纯暴力就能水过while(l<=r){int mid=(l+r)>>1;if(check(mid)) ans=mid,r=mid-1;else l=mid+1;}cout<<ans<<endl;}return 0;
}