wamp做的网站上传/微信营销的案例

思路：

这里不是求最小生成树了，而是求“边权值极差最小”的生成树，方法就是枚举每一个边，令他的边权最小，求最小生成树（所以边权比他小的边不参与），求与加入该生成树中的最大边权的极差即可。 

我的代码：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;const int MAXN=105;
const int MAXM=10000;struct edge
{int u,v,w;
}e[MAXM];bool cmp(edge a,edge b)  //重要！ 
{if(a.w<b.w)return true;elsereturn false;
}
//并查集（确定有无回路
int father[MAXN];
int get(int a)
{if(father[a]==a)return a;return father[a]=get(father[a]);
}void merge(int a,int b)
{a=get(a);b=get(b);if(a!=b)father[a]=b;
}int cnt=1;  //注意题目给的m和cnt值是不同意义的，m是方案数，因为无向图->双向边，则其实cnt=2*m 
void insert(int a,int b,int c)
{e[cnt].u=a;e[cnt].v=b;e[cnt].w=c;cnt++;
}
void insert2(int a,int b,int c)
{insert(a,b,c);insert(b,a,c);
}
int n;
int kruskal(int a) //返回以a的序号为起点边及之后的边构成的最小生成树的权值极差
{for(int i=1;i<=n;i++)father[i]=i;      //拜托！！！别忘了！！！并查集的初始化！ int res=0;int maxx=0; //记录最大权值的边（而最小权值的边已知是a序号的边 for(int i=a;i<=cnt && res<n-1;i++){if(get(e[i].u)!=get(e[i].v)){res++;merge(e[i].u,e[i].v);maxx=max(maxx,e[i].w);}}if(res==n-1)return maxx-e[a].w;elsereturn 0x3f3f3f3f;
} 
int main()
{int m; cin>>n>>m;while(m--){int a,b,c;cin>>a>>b>>c;insert2(a,b,c);}cnt--;sort(e+1,e+1+cnt,cmp); int minn=0x3f3f3f3f;for(int i=1;i<=cnt;i++){minn=min(kruskal(i),minn);  //关键语句。}if(minn==0x3f3f3f3f)cout<<-1;elsecout<<minn;return 0;
}