题目链接： http://poj.org/problem?id=3522
题目大意：
给定一个简单图，n个点，m条边( 1<=n<=100，0 ≤ m ≤ n(n − 1)/2 )，要求一颗生成树，使得其最大边与最小边的差值是所有生成树中最小的，输出最小的那个差值。
分析：
类似于kruskal算法求最小生成树，将所有边按权值大小排升序，e1,e2,e3,...em。
枚举每条边ei，对ei,ei+1,ei+2,ei+3...进行求生成树，不断更新差值得到最优值，具体见代码，复杂度不大会算。
注意：
开始我认为自己是水过的，因为我看到n是100的最大值，然后考虑到边是10000的最大值，便有了10000*10000的复杂度， 后来仔细想想，题目给的边数m<5000,那么自然有5000*5000不会超时。
另外，我开始有个想法是： 每枚举边ei，做完一遍生成树后，删除边ei，维护相关信息，然后再做生成树，这样就是从ei+1开始了，复杂的会大大降低，但是我还是想不出来如何删边且维护相关信息。
代码：
poj3522
1 /*3522 Accepted 320K 63MS C++ 1681B 2012-04-20 11:09:28*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <vector> 8 using namespace std; 9 10 #define mpair make_pair 11 #define pii pair<int,int> 12 #define MM(a,b) memset(a,b,sizeof(a)); 13 typedef long long lld; 14 typedef unsigned long long u64; 15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;} 16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;} 17 #define maxn 18 19 int n,m; 20 struct Edge{ 21 int u,v,w; 22 void read(){ 23 scanf("%d%d%d", &u, &v, &w); 24 } 25 bool operator<(Edge b)const{ 26 return w<b.w; 27 } 28 } edge[10050]; 29 30 const int inf= 200000000; 31 int fa[110]; 32 int find(int x){ 33 if( x==fa[x] ) return x; 34 else return fa[x]= find( fa[x] ); 35 } 36 int solve(){ 37 int ans= inf; 38 for(int k=1;k<=m;++k){ 39 for(int i=1;i<=n;++i) fa[i]= i; 40 int mmin= inf, mmax= -inf; 41 int cnt= 0; 42 43 for(int i=k;i<=m;++i){ 44 int x= edge[i].u, y= edge[i].v; 45 int fx= find(x), fy= find(y); 46 if( fx!=fy ){ 47 fa[fy]= fx; 48 up_min( mmin, edge[i].w ); 49 up_max( mmax, edge[i].w ); 50 if( ++cnt == n-1 ) break; 51 if( mmax-mmin >= ans ) break; /// 52 } 53 } 54 if( cnt == n-1 ) up_min( ans, mmax-mmin ); 55 } 56 return ans; 57 } 58 59 int main() 60 { 61 while( cin>>n>>m, (n+m) ){ 62 for(int i=1;i<=m;++i) 63 edge[i].read(); 64 sort( edge+1, edge+1+m ); 65 66 int ans= solve(); 67 if( ans!=inf ) cout<< ans <<endl; 68 else puts("-1"); 69 } 70 }