自动搬运

查看原文

来自洛谷，原作者为

	dailt **

搬运于2025-08-24 21:38:24，当前版本为作者最后更新于2018-10-02 13:05:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题可以用最小生成树做

这个题是让我们找一条s,t的路径 ,使得这条路上的最大边和最小边的比值最小

那我们可以先固定一条最大边，然后不断向其中添加小边直到s，t联通

由于我们可以将小边从大到小枚举，每次判断s,t是否联通

那s,t一旦联通，此时的最大边和最小边就是一组可能的解啦

然后我们枚举所有最大边，将所有可行解找到，然后将他们比较一下就得出最优解啦

#include <iostream>
#include <cstdio>
#include <algorithm> 
#define re register		//放在循环前可以让你的循环更快一点 
using namespace std;
int n,m,fa[1010],s,t,rn,cnt,ansnum,vis[1010];
double ans=50000;
struct edge{int u,v,w;}e[10100];
struct anss{int maxx,minn;}aa[200000];
int gcd(int a,int b){		//最大公约数 约分用的~ 
	if(b==0)	return a;
	else return gcd(b,a%b); 
}
int getf(int a){	//找爹  顺便路径压缩一下 
	if(fa[a]==a)	return a;
	return fa[a]=getf(fa[a]);
} 
int cmp(edge a,edge b){return a.w<b.w;}
int main(){
	scanf("%d%d",&n,&m);
	for(re int i=1;i<=n;++i)	fa[i]=i,vis[i]=1;
	for(re int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[i].u=u,e[i].v=v,e[i].w=w;
		int fu=getf(u),fv=getf(v);//先把所有边连起来看看 s 和 t 是否联通 
		if(fu!=fv)	fa[fu]=fv;
	}
	scanf("%d%d",&s,&t);
	if(getf(s)!=getf(t)){			//判断是否联通 
		cout<<"IMPOSSIBLE";
		return 0;
	}
	int fs=getf(s);
	for(re int i=1;i<=n;++i)
		if(getf(i)!=fs)	vis[i]=0;		//去掉没用的点（就是和s,t不连通的点 
	for(re int i=1;i<=n;++i)	fa[i]=i;	
	sort(e+1,e+m+1,cmp);
	for(re int i=1;i<=m;++i){			//固定最大边 
		if(!vis[e[i].u]||!vis[e[i].v])	continue;	//既然和s,t不连通那就不用这条边 
		for(re int j=1;j<=n;++j)	fa[j]=j; //记得初始化fa哦 
		for(re int j=i;j>=1;j--){		//寻找使s,t联通的最小边 
			int u=e[j].u,v=e[j].v;
			if(!vis[u]||!vis[v])	continue;
			int fu=getf(u),fv=getf(v);
			if(fu!=fv){
				fa[fu]=fv;
				int fs=getf(s),ft=getf(t);
				if(fs==ft){				//找到最小边 
					aa[++cnt]=(anss){e[i].w,e[j].w};//添加到可行解中 
					break;	 
				} 
			}
		}
	}
	for(re int i=1;i<=cnt;++i){   //寻找并记录最优解 
		if(((double)aa[i].maxx/(double)aa[i].minn)<ans){
			ans=((double)aa[i].maxx/(double)aa[i].minn);
			ansnum=i;
		} 
	}
	if((aa[ansnum].maxx%aa[ansnum].minn)==0){//最优解是整数 
		cout<<aa[ansnum].maxx/aa[ansnum].minn;
	}
	else{//最优解不是整数 
		int a1=aa[ansnum].maxx/gcd(aa[ansnum].maxx,aa[ansnum].minn);
		int a2=aa[ansnum].minn/gcd(aa[ansnum].maxx,aa[ansnum].minn);
		cout<<a1<<"/"<<a2;
	}
	return 0;
}