Description
给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T
，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出
这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。
Input
第一行包含两个正整数，N和M。下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向
公路，车辆必须以速度v在该公路上行驶。最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速
度比最小的路径。s和t不可能相同。
1<N<=500,1<=x,y<=N，0<v<30000，0<M<=5000，可能出现自环
Output
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一
个既约分数。
Sample Input
【样例输入1】
4 2
1 2 1
3 4 2
1 4
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
3 3
1 2 10
1 2 5
2 3 8
1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3
3 2
1 2 2
2 3 4
1 3
Sample Output
【样例输出1】
IMPOSSIBLE
IMPOSSIBLE
【样例输出2】
5/4
5/4
【样例输出3】
2
2
HINT
Source
Solution
首先把边按边权排序
第一种方法：枚举第一条边是哪条，之后从这条边开始做$Kruskal$，直到$S$与$T$联通或所有边都用完
因为最小生成树可以保证最大边权尽量小，所以在最小边权指定的情况下可以找到比值最小的情况，复杂度$O(m^2)$
（$Kruskal$不好玩，我们来玩$LCT$吧）
第二种方法：我们用$LCT$维护最小生成树，按顺序插入边，当新插入的边的两端已经在树上时，把边权最小的边断开，再把这条边插进去
联通性什么的都挺好判断的不用我多说了吧，复杂度是$O(mlog^2n)$的
（好像有一些细节没讲，算了不管啦）
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int u, v, w;
bool operator< (const edge &rhs) const
{
return w < rhs.w;
}
}e[];
struct LCT
{
int c[], fa, rev, val, mn, mx;
int& operator[] (int x)
{
return c[x];
}
}a[];
int sta[], top; int gcd(int x, int y)
{
return y ? gcd(y, x % y) : x;
} void push_up(int k)
{
int c0 = a[k][], c1 = a[k][];
a[k].mn = a[k].val ? k : , a[k].mx = k;
if(a[a[c0].mn].val && a[a[c0].mn].val < a[a[k].mn].val)
a[k].mn = a[c0].mn;
if(a[a[c0].mx].val > a[a[k].mx].val) a[k].mx = a[c0].mx;
if(a[a[c1].mn].val && a[a[c1].mn].val < a[a[k].mn].val)
a[k].mn = a[c1].mn;
if(a[a[c1].mx].val > a[a[k].mx].val) a[k].mx = a[c1].mx;
} void push_down(int k)
{
if(a[k].rev)
{
swap(a[k][], a[k][]), a[k].rev = ;
a[a[k][]].rev ^= , a[a[k][]].rev ^= ;
}
} bool isroot(int x)
{
return a[a[x].fa][] != x && a[a[x].fa][] != x;
} void rotate(int x)
{
int y = a[x].fa, z = a[y].fa, dy = a[y][] == x;
if(!isroot(y)) a[z][a[z][] == y] = x;
a[y][dy] = a[x][!dy], a[a[x][!dy]].fa = y;
a[x][!dy] = y, a[y].fa = x, a[x].fa = z;
push_up(y);
} void splay(int x)
{
sta[top = ] = x;
for(int i = x; !isroot(i); i = a[i].fa)
sta[++top] = a[i].fa;
while(top)
push_down(sta[top--]);
while(!isroot(x))
{
int y = a[x].fa, z = a[y].fa;
if(!isroot(y))
if(a[y][] == x ^ a[z][] == y) rotate(x);
else rotate(y);
rotate(x);
}
push_up(x);
} void access(int x)
{
for(int i = ; x; x = a[x].fa)
splay(x), a[x][] = i, i = x;
} void make_root(int x)
{
access(x), splay(x), a[x].rev ^= ;
} void link(int x, int y)
{
make_root(x), a[x].fa = y;
} void cut(int x, int y)
{
make_root(x), access(y), splay(y);
a[y][] = a[x].fa = , push_up(y);
} int find_root(int x)
{
access(x), splay(x);
while(a[x][])
x = a[x][];
return x;
} int main()
{
int n, m, u, v, sss, ttt, mx = , mn = , tmp;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; ++i)
{
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
if(e[i].u == e[i].v) --i, --m;
}
scanf("%d%d", &sss, &ttt);
sss += m, ttt += m;
sort(e + , e + m + );
a[].val = , a[].mx = ;
for(int i = ; i <= m + n; ++i)
a[i].val = e[i].w, push_up(i);
for(int i = ; i <= m; ++i)
{
u = e[i].u + m, v = e[i].v + m;
if(find_root(u) == find_root(v))
{
make_root(u), access(v), splay(v);
tmp = a[v].mn;
cut(e[tmp].u + m, tmp);
cut(e[tmp].v + m, tmp);
}
link(u, i), link(v, i);
if(find_root(sss) != find_root(ttt)) continue;
make_root(sss), access(ttt), splay(ttt);
if(1.0 * a[a[ttt].mx].val / a[a[ttt].mn].val < 1.0 * mx / mn)
mx = a[a[ttt].mx].val, mn = a[a[ttt].mn].val;
}
tmp = gcd(mx, mn), mx /= tmp, mn /= tmp;
if(mx == ) puts("IMPOSSIBLE");
else if(mn == ) printf("%d\n", mx);
else printf("%d/%d\n", mx, mn);
return ;
}