#kruskal#SSL 1312 2461 洛谷 2502 旅行

本文主要是介绍#kruskal#SSL 1312 2461 洛谷 2502 旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

选择行使过程中最大速度和最小速度的比尽可能小的路线

---

分析

运用Kruskal，首先枚举一条边，然后找一个最小生成树。

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
struct node{int x,y,w;}e[5001]; bool flag;
int n,m,f[501],st,a,b,en,nod; double mn=2147483647;
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int getf(int u){return (f[u]==u)?u:f[u]=getf(f[u]);}
bool cmp(node x,node y){return x.w<y.w;}
void tn(int &a,int &b){a=in();b=in();}
int main(){tn(n,m); for (int i=1;i<=m;i++) tn(e[i].x,e[i].y),e[i].w=in();stable_sort(e+1,e+1+m,cmp); tn(st,en);for (int i=1;i<m;i++){for (int j=1;j<=n;j++) f[j]=j; nod=i-1; flag=0;while (1){if (getf(st)==getf(en)) {flag=1;break;}//连通就可以退出if (nod>m) break;int k1=getf(e[++nod].x);int k2=getf(e[nod].y);if (k1!=k2) f[k1]=k2;}if (flag&&(double)e[nod].w/e[i].w<mn)mn=(double)e[nod].w/e[i].w,a=e[nod].w,b=e[i].w;}if (mn==2147483647) puts("IMPOSSIBLE");else{int gcd=__gcd(a,b);//求最小公倍数printf("%d",a/gcd);if (a%b) printf("/%d",b/gcd); }return 0;
} 

这篇关于#kruskal#SSL 1312 2461 洛谷 2502 旅行的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---