首页 > 代码库 > BZOJ 1050 旅行comf(枚举最小边-并查集)
BZOJ 1050 旅行comf(枚举最小边-并查集)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1050
题意:给出一个带权图。求一条s到t的路径使得这条路径上最大最小边的比值最小?
思路:将边排序。枚举最小边,然后将边一个一个插到并查集里,s和t联通时计算更新答案。
struct node{ int u,v,w; void get() { RD(u,v,w); }};int cmp(node a,node b){ return a.w<b.w;}int n,m,s,t;node a[N*10];i64 Gcd(i64 x,i64 y){ return !y?x:Gcd(y,x%y);}int S[N];int get(int x){ if(S[x]!=x) S[x]=get(S[x]); return S[x];}void Union(int x,int y){ x=get(x); y=get(y); if(x!=y) S[x]=y;}int main(){ RD(n,m); int i,j; FOR1(i,m) a[i].get(); sort(a+1,a+m+1,cmp); RD(s,t); i64 ansX=1,ansY=30000,temp; int flag=0; FOR1(i,m) { FOR1(j,n) S[j]=j; FOR(j,i,m) { Union(a[j].u,a[j].v); if(get(s)==get(t)) break; } if(j<=m) { flag=1; if(ansY*a[i].w>ansX*a[j].w) { ansX=a[i].w; ansY=a[j].w; } } } if(!flag) puts("IMPOSSIBLE"); else { temp=Gcd(ansX,ansY); ansX/=temp; ansY/=temp; if(ansX==1) PR(ansY); else printf("%lld/%lld\n",ansY,ansX); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。