这是建空间后做的第一道题啊= =好水

排序，枚举最小边，然后并查集求出联通时的最大边

或者排次序，从小到大插边，如果插边时最小的边拿掉不会使s与t不联通，就删去。

 

code：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; struct node{      int x,y,dist; }a[5010]; int n,m,s,t,f[510],ansi,ansa; bool cmp(node x,node y){ return x.dist<y.dist;} int find( int x){ if (x!=f[x]) f[x]=find(f[x]); return (f[x]);} int gcd( int x, int y){      if (!y) return x;      return gcd(y,x %y); } int main(){      scanf ( "%d%d" ,&n,&m);      for ( int i=1;i<=m;i++) scanf ( "%d%d%d" ,&a[i].x,&a[i].y,&a[i].dist);      sort(a+1,a+1+m,cmp);      scanf ( "%d%d" ,&s,&t);      ansi=a[1].dist;ansa=40000;      for ( int i=1;i<=n;i++) f[i]=i;      for ( int i=1;i<=m;i++) {          int x=find(a[i].x),y=find(a[i].y);          if (x!=y) f[x]=y;          x=find(s);y=find(t);          if (x==y) {              ansa=a[i].dist;              break ;          }      }      if (ansa==40000) { printf ( "IMPOSSIBLE\n" ); return 0;}      for ( int i=2;i<=m;i++) {          for ( int j=1;j<=n;j++) f[j]=j;          for ( int j=i;j<=m;j++) {              int x=find(a[j].x),y=find(a[j].y);              if (x!=y) f[x]=y;              x=find(s);y=find(t);              if (x==y) {                  if (ansa*1.0/ansi>a[j].dist*1.0/a[i].dist) {ansa=a[j].dist;ansi=a[i].dist;}                  break ;              }          }      }      int t=gcd(ansa,ansi);      if (ansa*1.0/ansi==ansa/ansi) printf ( "%d\n" ,ansa/ansi);      else printf ( "%d/%d" ,ansa/t,ansi/t);      return 0; }