洛谷P2502 [HAOI2006]旅行题解

题目链接：P2502 [HAOI2006]旅行

题意：

Z 小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z 小镇附近共有 \(n\) 个景点（编号为 \(1,2,3,\ldots,n\)），这些景点被 \(m\) 条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。

也许是为了保护该地的旅游资源，Z 小镇有个奇怪的规定，就是对于一条给定的公路 \(r_i\)，任何在该公路上行驶的车辆速度必须为 \(v_i\)。

速度变化太快使得游客们很不舒服，因此从一个景点前往另一个景点的时候，大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

输入格式：

第一行包含两个正整数 \(n,m\)。

接下来的 \(m\) 行每行包含三个正整数 \(x,y,v\)。表示景点 \(x\) 到景点 \(y\) 之间有一条双向公路，车辆必须以速度 \(v\) 在该公路上行驶。

最后一行包含两个正整数 \(s,t\)，表示想知道从景点 \(s\) 到景点 \(t\) 最大最小速度比最小的路径。\(s\) 和 \(t\) 不可能相同。

输出格式：

如果景点 \(s\) 到景点 \(t\) 没有路径，输出IMPOSSIBLE。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

数据范围：

对于 \(100\%\) 的数据，\(1 \le x,y \le n \le 500\)，\(1 \le v < 3 \times 10^4\)，\(1 \le m \le 5 \times 10^3\)，\(x \ne y\)。

这种经典二维限制的题目，往往是枚举一维，维护一维。

在这题中，就是固定 \(\min\) ，然后处理 \(\max\)

无解显然是把所有边全加进去 \(s,t\) 都不连通，用并查集很好维护

具体地，按边权从小到大依次考虑每条边作为 \(\min\) ，

然后从小到大不断加入大于它的边，直到 \(s,t\) 连通。

此时最后加入的一条边就是 \(\max\) ，但是我们枚举的 \(\min\) 不一定是。

这不要紧，因为我们会考虑所有的边，所以一定不会漏掉更优的解。

时间复杂度 \(O(m^2)\) ，还是比较灵活的一道题。

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(5e2+15))
#define M ((int)(5e3+15))

double res=1e233;
int n,m,s,t,a,b,f[N],r[N];
struct Edge{int u,v,w;} e[M];
void init(int n) {for(int i=1; i<=n; i++) f[i]=i,r[i]=1;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int gcd(int a,int b){return b==0 ? a : gcd(b,a%b);}
void merge(int u,int v)
{
    int x=find(u), y=find(v);
    if(x==y) return;
    if(r[x] < r[y]) f[x]=y;
    else f[y]=x,r[x]+=(r[x]==r[y]);
}
void kruskal(int i)
{
    for(int j=i; j<=m; j++)
    {
        merge(e[j].u, e[j].v);
        if(find(s) == find(t))
        {
            double tmp=1.0*e[j].w/e[i].w;
            if(res > tmp) res=tmp,a=e[j].w,b=e[i].w;
            return;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; init(n);
    for(int i=1,u,v,w; i<=m; i++)
    {
        cin >> u >> v >> w;
        e[i]={u,v,w}; merge(u,v);
    }
    cin >> s >> t;
    if(find(s) != find(t)) return cout << "IMPOSSIBLE\n",0;
    sort(e+1,e+1+m,[](Edge a,Edge b){return a.w<b.w;});
    for(int i=1; i<=m; i++) init(n),kruskal(i);
    int g=gcd(a,b);
    // cout << a << " " << b << '\n';
    if(a/b*b == a) cout << a/b << '\n';
    else cout << a/g << '/' << b/g << '\n';
    return 0;
}