记录编号	274130	评测结果	AAAAAAAAAA
题目名称	1301.[HAOI 2006]旅行	最终得分	100
用户昵称	KCkwok	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2016-06-27 12:02:51	内存使用	0.39 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3fffffff
int n,m,s,t;
struct data{
	int a,b;
	int v;
}e[5010];
int f[5010];

int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline void init(){for(int i=1;i<=n;i++)f[i]=i;}
inline int cmp(data a,data b){return a.v<b.v;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline void unionn(int a,int b){
	a=find(a);b=find(b);
	if(a!=b)f[a]=b;
}

int main(){
	freopen("comf.in","r",stdin);
	freopen("comf.out","w",stdout); 
	int mx,mn,aa,bb,r,start;
	int ansmx=1,ansmn=0;
	int i,j;
	cin>>n>>m;
	for(i=1;i<=m;i++){
		cin>>e[i].a>>e[i].b>>e[i].v;
	}
	cin>>s>>t;
	sort(e+1,e+1+m,cmp);//边按权值排序，标号1~m
	start=1;//初始化一个枚举起点start=1 
	while(start<=m){
		mn=mx=-1;
		init();//初始化并查集 
		for(i=start;i<=m;i++){//从start开始顺推，利用并查集加边，直到s,t连通 
			unionn(e[i].a,e[i].b);
			if(find(s)==find(t)){mx=e[i].v;break;}//记为r 
		}
		if(mx==-1){
			if(!ansmn){cout<<"IMPOSSIBLE";return 0;}
			else break;
		}
		init();//初始化并查集 
		for(;i>=1;i--){//从r逆推，利用并查集加边，直到s,t连通 
			unionn(e[i].a,e[i].b);
			if(find(s)==find(t)){mn=e[i].v;break;}//得到l 
		}
		start=i+1;
		if(mn==-1){
			if(!ansmn){cout<<"IMPOSSIBLE";return 0;}
			else break;
		}
		r=gcd(mx,mn);mx/=r;mn/=r;
		if(ansmx*mn>ansmn*mx){ansmn=mn;ansmx=mx;}//如果是更优解则更新 
	}
	if(ansmn==1)cout<<ansmx;
	else cout<<ansmx<<"/"<<ansmn<<endl;
	return(0);
}