10pts求助
查看原帖
10pts求助
665933
__LZH__楼主2023/5/20 11:18
#include<bits/stdc++.h>
using namespace std;
long long f[11451400],n,m,x,y,u[11451400];
int q=INT_MAX,p=INT_MIN;
int find(int x){
	if(x==f[x]){
		return x;
	}else{
		return f[x]=find(f[x]);
	}
}
int gcd(int a,int b){
	if(b==0){
		return a;
	}
	return gcd(b,a%b);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y>>u[i];
		x=find(x);
		y=find(y);
		if(x!=y){
			f[x]=y;
			p=max(p,u[i]);
		}		
	}
	int s,t;
	cin>>s>>t;
	if(f[find(s)]!=find(t)){
		puts("IMPOSSIBLE");
	}else{
		sort(u+1,u+m+1);
		q=u[m-1];
		if(p%q!=0){
			x=gcd(p,q);
			p/=x,q/=x;
			cout<<p<<'/'<<q<<endl;
			return 0;
		}else{
			cout<<p/q<<endl;
		}
	}
	return 0;
}
2023/5/20 11:18
加载中...