题目链接:http://nyoj.top/problem/711

  • 内存限制:64MB 时间限制:5000ms

题目描述:

异形卵潜伏在某区域的一个神经网络中。其网络共有N个神经元（编号为1,2,3,…,N），这些神经元由M条通道连接着。两个神经元之间可能有多条通道。异形卵可以在这些通道上来回游动，但在神经网络中任一条通道的游动速度必须是一定的。当然异形卵不希望从一条通道游动到另一条通道速度变化太大，否则它会很不舒服。

现在异形卵聚居在神经元S点，想游动到神经元T点。它希望选择一条游动过程中通道最大速度与最小速度比尽可能小的路线，也就是所谓最舒适的路线。

输入描述:

第一行： K 表示有多少组测试数据。 
接下来对每组测试数据：
第1行:       N  M
第2~M+1行： Xi  Yi  Vi   (i=1,…..,M)
表示神经元Xi 到神经元Yi之间通道的速度必须是Vi
最后一行：     S  T     ( S  T )

【约束条件】
 2≤K≤5   1<N≤500   0<M≤5000   1≤ Xi, Yi , S , T ≤N   0< Vi <30000，
Vi是整数。数据之间有一个空格。

输出描述:

对于每组测试数据，输出一行：如果神经元S到神经元T没有路线，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

样例输入:

2
3 2
1 2 2
2 3 4
1 3
3 3
1 2 10
1 2 5
2 3 8
1 3

样例输出:

2
5/4

解题思路

我们可以先按速度从小到大排一下序，然后遍历一下，利用并查集的性质，只要没有连通的就连通，如果s到t已经连通，就求出它们最小的比值，然后一直这样遍历。

#include <bits/stdc++.h>
using namespace std;
const int inf = 99999999;
struct edge {
    int x, y, v;
}e[5005];
int f[505];
bool cmp(edge A, edge B) {
    return A.v < B.v;
}
int getf(int v) {
    if (f[v] != v)
        return f[v] = getf(f[v]);
    return v;
}
int gcd(int a, int b) {
    if (!b)
        return a;
    return gcd(b, a % b);
}
int main() {
    int t, n, m, ss, tt, max_, min_;
    scanf("%d", &t);
    while (t--) {
        min_ = 1;
        max_ = inf;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].v);
        scanf("%d%d", &ss, &tt);
        sort(e, e + m, cmp);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <= n; j++)
                f[j] = j;
            for (int j = i; j < m; j++) {
                int t1 = getf(e[j].x);
                int t2 = getf(e[j].y);
                if (t1 != t2)
                    f[t1] = t2;
                if (getf(ss) == getf(tt)) {
                    if (max_ * e[i].v > min_ * e[j].v){
                        max_ = e[j].v;
                        min_ = e[i].v;
                    }
                    break;
                }
            }
        }
        if (max_ < inf) {
            int gcd_ = gcd(max_, min_);
            if (max_ % min_)
                printf("%d/%d\n", max_ / gcd_, min_ / gcd_);
            else printf("%d\n", max_ / min_);
        }
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}