题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1050
枚举最大最小边，然后并查集维护连通性即可。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define inf 0x7fffffff
#define MAXN 510
#define MAXM 5010
struct Edge {
int s , t , d ;
bool operator < ( const Edge &a ) const {
return d < a.d ;
}
} e[ MAXM ] ;
int n , m , S , T ;
struct Uset {
int father[ MAXN ] , size[ MAXN ] ;
void Init( ) {
memset( father , 0 , sizeof( father ) ) ;
for ( int i = 0 ; i < MAXN ; ++ i ) size[ i ] = 1 ;
}
int Find( int x ) {
int i , j = x ;
for ( i = x ; father[ i ] ; i = father[ i ] ) ;
while ( father[ j ] ) {
int k = father[ j ] ; father[ j ] = i ; j = k ;
}
return i ;
}
bool check( int x , int y ) {
return Find( x ) == Find( y ) ;
}
void Union( int x , int y ) {
if ( Find( x ) != Find( y ) ) {
if ( size[ Find( x ) ] < size[ Find( y ) ] ) swap( x , y ) ;
size[ Find( x ) ] += size[ Find( y ) ] ;
father[ Find( y ) ] = Find( x ) ;
}
}
} us ;
int gcd( int x , int y ) {
if ( x < y ) swap( x , y ) ;
while ( y ) {
int k = x % y ;
x = y ; y = k ;
}
return x ;
}
int main( ) {
scanf( "%d%d" , &n , &m ) ;
us.Init( ) ;
for ( int i = 0 ; i ++ < m ; ) {
scanf( "%d%d%d" , &e[ i ].s , &e[ i ].t , &e[ i ].d ) ;
us.Union( e[ i ].s , e[ i ].t ) ;
}
scanf( "%d%d" , &S , &T ) ;
if ( ! us.check( S , T ) ) {
printf( "IMPOSSIBLE\n" ) ; return 0 ;
}
sort( e + 1 , e + m + 1 ) ;
int rec = inf , ret = 1 ;
for ( int i = 0 ; i ++ < m ; ) {
us.Init( ) ;
for ( int j = i ; j <= m ; ++ j ) {
us.Union( e[ j ].s , e[ j ].t ) ;
if ( us.check( S , T ) ) {
if ( double( rec ) / double( ret ) > double( e[ j ].d ) / double( e[ i ].d ) ) {
rec = e[ j ].d , ret = e[ i ].d ;
}
break ;
}
}
}
if ( ! ( rec % ret ) ) printf( "%d\n" , rec / ret )
; else printf( "%d/%d\n" , rec / gcd( rec, ret ) , ret / gcd( rec , ret ) ) ;
return 0 ;
}
