网站开发就是ssh吗,品牌设计全案,网站建设合同 文库,龙江网站设计Z 小镇是一个景色宜人的地方#xff0c;吸引来自各地的观光客来此旅游观光。Z 小镇附近共有 n 个景点#xff08;编号为 1,2,3,…,n#xff09;#xff0c;这些景点被 m 条道路连接着#xff0c;所有道路都是双向的#xff0c;两个景点之间可能有多条道路。
也许是为了保…Z 小镇是一个景色宜人的地方吸引来自各地的观光客来此旅游观光。Z 小镇附近共有 n 个景点编号为 1,2,3,…,n这些景点被 m 条道路连接着所有道路都是双向的两个景点之间可能有多条道路。
也许是为了保护该地的旅游资源Z 小镇有个奇怪的规定就是对于一条给定的公路 ri任何在该公路上行驶的车辆速度必须为 vi。
速度变化太快使得游客们很不舒服因此从一个景点前往另一个景点的时候大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线也就是所谓最舒适的路线。
输入描述
第一行包含两个正整数 n,m。
接下来的 m 行每行包含三个正整数 x,y,v。表示景点 x 到景点 y 之间有一条双向公路车辆必须以速度 v 在该公路上行驶。
最后一行包含两个正整数 s,t表示想知道从景点 s 到景点 t 最大最小速度比最小的路径。s 和 t 不可能相同。
其中1 ≤ x , y ≤ n ≤ 5001 ≤ v 3 × 10^41 ≤ m ≤ 5 × 10^3x ! y。
输出描述
如果景点 s 到景点 t 没有路径输出IMPOSSIBLE。否则输出一个数表示最小的速度比。如果需要输出一个既约分数。
输入输出样例
示例 1 输入 4 2
1 2 1
3 4 2
1 4输出 IMPOSSIBLE 解题思路
这是一道比较有意思的最小生成树不同于普通的最短连通这里可能需要求出所有的生成树。
这道题的关键点不是要求出包含n-1条边的最小生成树而是只需要求出指定起点到终点的生成树就可以了并且这里不用判断新增的边是否构成圈无脑merge即可因为多余的边并不会影响到我们的答案。
Kruskal算法在这里要比Prim算法好得多因为Kruskal对边权值先进行了排序我们就可以围绕最大最小值之比最小来做文章并且可以很轻松的利用并查集判断起点终点的包含性。
考虑到如果使用双指针对并查集的拆分可能会比较困难简单的来说只需要从小到大不断地将每一条边作为最短边构造出每一颗满足包含指定起点和终点的最小生成树即可。
import java.io.*;
import java.util.*;public class Main {static int n, m, st, ed;static int[] s;static long INF Long.MAX_VALUE 1;public static void main(String[] args) throws IOException {Scanner sc new Scanner(System.in);n sc.nextInt();m sc.nextInt();Edge[] edges new Edge[m];for (int i 0; i m; i) {int u sc.nextInt();int v sc.nextInt();int w sc.nextInt();edges[i] new Edge(u, v, w);}Arrays.sort(edges, Comparator.comparingInt((Edge e) - e.w));st sc.nextInt();ed sc.nextInt();int min, max, minAns 1, maxAns 1000000;for (int i 0; i m; i) {min Integer.MAX_VALUE;max 0;set_init();for (int j i; j m; j) {int u edges[j].u;int v edges[j].v;int w edges[j].w;set_merge(u, v);min Math.min(min, w);max Math.max(max, w);if (set_find(st) set_find(ed)) {if (1.0 * max / min 1.0 * maxAns / minAns) {maxAns max;minAns min;break;}}}}if (maxAns ! 1000000) {if (maxAns % minAns 0) {System.out.print(maxAns / minAns);} else {int t gcd(maxAns, minAns);System.out.print((maxAns / t) / (minAns / t));}} else {System.out.print(IMPOSSIBLE);}}public static int gcd(int m, int n) {return m % n 0 ? n : gcd(n, m % n);}public static void set_init() {s new int[n 1];for (int i 0; i n; i) {s[i] i;}}public static int set_find(int x) {return s[x] x s[x] ? s[x] : set_find(s[x]);}public static void set_merge(int x, int y) {s[set_find(y)] set_find(x);}
}class Edge {int u, v, w;public Edge(int u, int v, int w) {super();this.u u;this.v v;this.w w;}}
