HYSBZ - 1050(旅行comf Java实现)
解法：枚举每一条边，对于这条边，我们需要找到集合中和其值相差最小的最大边，这个集合是指与包括i边在内的ST联通集。对于这一要求，我们只需对所有的边进行从小到大的排序，那么从i边开始，一条条地加入并查集，一旦形成上述的联通集，立刻停止。
import java.io.*;
import java.util.*;
public class Main{
private static class edge{
int x,y,v;
}
private static class cmp implements Comparator<edge>{
@Override
public int compare(edge a,edge b){
return a.v<b.v?-1:1;
}
}
private static int fa[]=new int[505];
private static int Find(int x){
if(fa[x]==-1) return x;
return fa[x]=Find(fa[x]);
}
private static int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
private static final int N=5000+5;
private static edge e[]=new edge[N];
public static void main(String[] args){
int n,m,s,t;
Scanner sc=new Scanner(new InputStreamReader(System.in));
n=sc.nextInt();m=sc.nextInt();
for(int i=0;i<m;i++){
e[i]=new edge();
e[i].x=sc.nextInt();
e[i].y=sc.nextInt();
e[i].v=sc.nextInt();
}
s=sc.nextInt();
t=sc.nextInt();
Arrays.sort(e,0,m,new cmp());
int x1=0,y1=0;
for(int i=0;i<m;i++){
int ma=-1;
Arrays.fill(fa,-1);
for (int j=i; j<m; j++){
int f1=Find(e[j].x),f2=Find(e[j].y);
if (f1==f2) continue;
fa[f1]=f2;
if (Find(s)==Find(t)){
ma=e[j].v;
break;
}
}
if (ma==-1&&i==0){
System.out.printf("IMPOSSIBLE\n");
System.exit(0);
}
if (ma==-1) break;
if (x1==0||x1*e[i].v>ma*y1){
x1=ma;y1=e[i].v;
}
}
int x=gcd(x1,y1);
if (x==y1) System.out.printf("%d\n",x1/y1);
else System.out.printf("%d/%d\n",x1/x,y1/x);
sc.close();
}
}