WA六个点,求助!!!
查看原帖
WA六个点,求助!!!
734982
bobi0577楼主2023/8/13 09:31
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,fa[505],ansx[5005],ansy[5005],ans;
double mn=1e9;
bool bflag=false;
struct data{
	int x,y,z;
}a[5005];
bool cmp(data q,data p){
	return q.z<p.z;
}
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void unin(int x,int y){
	if(find(x)!=find(y))fa[find(x)]=find(y);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	cin>>s>>t;
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			fa[j]=j;
		}
		bool flag=false,bo=true;
		int k=i;
		while(!flag){
			flag=true;
			if(k>n){
				bo=false;
				break;
			}
			unin(a[k].x,a[k].y);
			if(find(s)!=find(t))flag=false;
			k++;
		}
		k--;
		if(bo)bflag=true;
		ansx[i]=a[k].z;
		ansy[i]=a[i].z;
		if(!bo)ansx[i]=1e9,ansy[i]=1;
	}
	for(int i=1;i<=m;i++){
		if(ansx[i]*1.0/ansy[i]<mn){
			mn=ansx[i]*1.0/ansy[i];
			ans=i;
		}
	}
	if(!bflag)cout<<"IMPOSSIBLE";
	else{
		int q=ansx[ans],p=ansy[ans];
		if(q*1.0/p==q/p){
			cout<<q/p;
			return 0;
		}
		else{
			for(int i=2;i<=min(q,p);i++){
				while(q%i==0&&p%i==0){
					q/=i;
					p/=i;
				}
			}
			cout<<q<<'/'<<p;
		}
	}
}

求dalao相助!!!

2023/8/13 09:31
加载中...