求助,急!
查看原帖
求助,急!
906970
Jerry_Money楼主2024/8/4 14:34
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct sb{
	int x,y,z;
}e[200086];
int s,t,st;
bool cnm(sb x,sb y){
	return x.z<y.z;
}
int f[100086];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int minn,maxx;
struct FS{
	int a,b;
};
FS minfs(FS a,FS b){
	FS x=a,y=b;
	if(a.a==0&&a.b==0)return b;
	if(b.a==0&&b.b==0)return a;
	x.a*=__gcd(x.b,y.b);
	y.a*=__gcd(x.b,y.b);
	if(x.a>=y.a)return b;
	else return a;
}
FS yf(FS fs){
	int xx=__gcd(fs.a,fs.b);
	fs.a/=xx;
	fs.b/=xx;
	return fs;
}
FS fs;
bool _t;
void tree(){
	int ans=0;
	int tot=0;
	for(int i=1;i<=m;i++){
		if(e[i].z<minn)continue;
        int x=e[i].x,y=e[i].y;
        x=find(x),y=find(y);
		if(x==y){
			continue;
		}
		f[y]=x;
	    tot++;
	    ans=max(ans,e[i].z);
		if(tot==n-1){
			maxx=max(maxx,ans);
			_t=1;
			return;
			
		}
	}
	if(minn==e[1].z){
		cout<<"IMPOSSIBLE";
		exit(0);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y>>e[i].z;
	}
	cin>>s>>t;
	sort(e+1,e+1+m,cnm);
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)f[j]=j;
		_t=0;
		minn=e[i].z;
		tree();
		if(maxx!=0&&_t)fs=minfs(yf(FS({maxx,minn})),fs);
		
	}
	yf(fs);
	cout<<fs.a;
	if(fs.b!=1)cout<<"/"<<fs.b;
}
2024/8/4 14:34
加载中...