题目大意:
定义Slim span为一幅无向图的生成树,且它的值为最大的权减最小的权。现在让你求最小的Slim span
思路:
固定最小的边,枚举最大的边。然后看看哪个大就可以了~
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=100+10; int n,m,fa[MAXN]; int find(int cur) { return cur==fa[cur]? cur:fa[cur]=find(fa[cur]); } struct edge { int from,to,val; bool operator<(const edge& x)const { return val<x.val; } }e[MAXN*MAXN]; void init() { for(int i=1;i<=n;i++) fa[i]=i; } int kruskal(int i) { int res=0; int cnt=0; for(;i<m;i++) { int x=e[i].from,y=e[i].to; int root_x=find(x),root_y=find(y); if(root_x==root_y) continue; cnt++; fa[root_x]=root_y; res=e[i].val; } if(cnt!=n-1) return -1; return res; } int main() { while(~scanf("%d%d",&n,&m),n||m) { for(int i=0;i<m;i++) scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val); sort(e,e+m); init(); int ans=kruskal(0); if(ans==-1) { printf("-1\n"); continue; } ans-=e[0].val; for(int i=1;i<m;i++) { init(); int res=kruskal(i); //固定最小边,枚举最大边 if(res==-1) break; ans=min(ans, res-e[i].val); } printf("%d\n",ans); } return 0; }