蓝桥杯第859题——旅行

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 ≤ 500，1 ≤ v < 3 × 10^4，1 ≤ m ≤ 5 × 10^3，x != 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;
    }
    
}