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不可能相同。
Output
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。
Sample Input
【样例输入1】
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 2
1 2 2
2 3 4
1 3
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 2
1 2 2
2 3 4
1 3
Sample Output
【样例输出1】
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2
HINT
【数据范围】
1< N < = 500
1 < = x, y < = N，0 < v < 30000，x ≠ y
0 < M < =5000
Source
自己YY了一个做法，感觉复杂度有点不太对，但跑起来还是飞快的。
枚举最大的边权，然后根据当前求出的最优答案找出最小边权，在这个范围内的边中做一遍最大生成树。先用并查集判断两点是否联通：不联通直接再见；否则再找出两点路径的最大值来更新答案。应该很好写，我都能想出来。
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std; #define inf (1<<30)
#define maxn 510
#define maxm 5010 int n,m,up,down,side[maxn],toit[maxn*],next[maxn*];
int s,t,tot,cnt,father[maxn],bac[maxm],arr[maxn],len[maxn*];
double ans = (double)inf; bool in[maxn];
struct EDGE
{
int x,y,v;
friend inline bool operator <(const EDGE &a,const EDGE &b) { return a.v > b.v; }
}edge[maxm],temp[maxm]; inline void init() { for (int i = ;i <= n;++i) father[i] = i; } inline int find(int a) { if (father[a]!=a) father[a] = find(father[a]); return father[a]; } inline int gcd(int a,int b) { return b?gcd(b,a%b):a; } inline void add(int a,int b,int c)
{
next[++cnt] = side[a]; side[a] = cnt;
toit[cnt] = b; len[cnt] = c;
} inline void ins(int a,int b,int c) { add(a,b,c); add(b,a,c); } inline int bfs()
{
int team[maxn],*head,*tail;
head = tail = team; memset(in,false,n+);
*(++tail) = s; in[s] = true; arr[s] = inf;
while (head != tail)
{
int now = *(++head);
if (now == t) return arr[t];
for (int i = side[now];i;i = next[i])
if (!in[toit[i]]) *(++tail) = toit[i],arr[toit[i]] = min(arr[now],len[i]),in[toit[i]] = true;
}
} inline void work(int key)
{
int lim = key/ans,all = ,k = ;
for (int i = ;i <= m;++i) if (edge[i].v>lim&&edge[i].v <= key) temp[++all] = edge[i];
init(); memset(side,,*(n+)); cnt = ;
sort(temp+,temp+all+);
for (int i = ;i <= all;++i)
{
int r1 = find(temp[i].x),r2 = find(temp[i].y);
if (r1 != r2)
father[r1] = r2,ins(temp[i].x,temp[i].y,temp[i].v),++k;
if (k == n-) break;
}
if (find(s) != find(t)) return;
lim = bfs();
if ((1.0*key)/(1.0*lim) < ans) ans = (1.0*key)/(1.0*lim),up = key,down = lim;
} int main()
{
freopen("1050.in","r",stdin);
freopen("1050.out","w",stdout);
scanf("%d %d",&n,&m);
init();
for (int i = ;i <= m;++i)
{
int a,b,c; scanf("%d %d %d",&a,&b,&c);
edge[i] = (EDGE){a,b,c};
int r1 = find(a),r2 = find(b);
if (r1 != r2) father[r1] = r2;
bac[++tot] = c;
}
scanf("%d %d",&s,&t);
if (find(s) != find(t)) printf("IMPOSSIBLE\n"),exit();
sort(bac+,bac+tot+); tot = unique(bac+,bac+tot+)-bac-;
for (int i = tot;i;--i) work(bac[i]);
int d = gcd(up,down);
up /= d; down /= d;
if (down != ) printf("%d/%d",up,down);
else printf("%d",up);
fclose(stdin); fclose(stdout);
return ;
}