最小生成树+枚举。
题意是说在一个无向图的所有生成树中,选取最小“苗条”值的。
“苗条”的定义是生成树中权值最大的边 减去 权值最小的边的 值。
我的思路是 排序,然后从 0~m枚举。每次必然加入枚举的那一条边。
然后 向其左右分别 选择边加入。直到构成生成树,不能就返回INF。
其实我感觉我的代码有点问题,我没有比较左右当中谁更 接近 枚举的那条边。已经做好了WA的准备,没想到居然AC了。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; int fa[101]; struct lx { int u,v,len; }l[5001]; bool cmp(lx a,lx b) { return a.len<b.len; } int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } int Kruskal(int j) { int ans=0; int maxv,minv; int num=2; for(int i=1;i<=n;i++) fa[i]=i; int x=father(l[j].u); int y=father(l[j].v); fa[y]=x; maxv=minv=l[j].len; int i=1,L,R; while(num<n) { bool flagl=0,flagr=0; L=j-i,R=j+i; if(L>=0&&L<m)flagl=1; if(R>=0&&R<m)flagr=1; int fu,fv; if(flagl) { fu=father(l[L].u); fv=father(l[L].v); if(fu!=fv) { fa[fv]=fu; minv=l[L].len; num++; } if(num>=n)break; } if(flagr) { fu=father(l[R].u); fv=father(l[R].v); if(fu!=fv) { fa[fv]=fu; maxv=l[R].len; num++; } if(num>=n)break; } i++; if(!flagl&&!flagr)return INF; } return max(maxv,minv)-min(maxv,minv); } int main() { while(scanf("%d%d",&n,&m),n||m) { for(int i=0;i<m;i++) scanf("%d%d%d",&l[i].u,&l[i].v,&l[i].len); sort(l,l+m,cmp); int ans=INF; for(int i=0;i<m;i++) { ans=min(ans,Kruskal(i)); } if(ans==INF)puts("-1"); else printf("%d\n",ans); } }
POJ 3522 Slim Span,布布扣,bubuko.com
原文:http://blog.csdn.net/dongshimou/article/details/37066485