这道题。。。一眼看出一个暴力思虑。。。那就是按照生成树。。。

排完序之后从当前边开始向后做生成树。。。

统计一下答案就好了。。。

结果。。。这就是正解。。。QVQ。。。smg。。。我去。。。

呆码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 99999999
#define MAXN 1010
#define unionn(x,y) fa[y]=x
#define eps 0.000001
using namespace std; int fa[MAXN],n,m,s,t,maxn,minx,ll=INF,rr=INF;
double ans=; struct asd{
int x,y,v;
} r[]; inline int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
} inline bool cmp(asd x,asd y)
{
return x.v<y.v;
} inline int gcd(int a,int b)
{
return b== ? a : gcd(b,a%b);
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d%d%d",&r[i].x,&r[i].y,&r[i].v);
scanf("%d%d",&s,&t);
sort(r+,r++m,cmp); for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++) fa[j]=j;
unionn(find(r[i].x),find(r[i].y));
minx=maxn=r[i].v;
if(find(s)==find(t))
{
double anss=ans;
ans=(double)maxn/minx;
if(ans-eps<anss-eps)
ll=maxn,rr=minx;
break;
}
for(int j=i+;j<=m;j++)
if(find(r[j].x)!=find(r[j].y))
{
unionn(find(r[j].x),find(r[j].y));
minx=min(minx,r[j].v);
maxn=max(maxn,r[j].v);
if(find(s)==find(t))
{
double anss=ans;
ans=(double)maxn/minx;
if(ans-eps<anss-eps)
ll=maxn,rr=minx;
else ans=anss;
break;
}
}
}
if(ll==INF) { printf("IMPOSSIBLE\n"); return ;}
if((double)ll/rr==ll/rr) printf("%d",ll/rr);
else
{
while(gcd(rr,ll)!=)
{
int mid=gcd(rr,ll);
ll/=mid; rr/=mid;
}
printf("%d/%d\n",ll,rr);
}
}

代码

不过细节比较多。。。要注意。。。

最新文章

  1. 地图、定位 CLLocationManager CLGeocoder CLPlacemark
  2. Python串口编程
  3. 迁移/home目录至新硬盘分区总结--无备份情况下
  4. [Qt] fontawesome图标
  5. 将Oracle JDBC驱动库安装到本地仓库
  6. android service和activity的通讯
  7. ArcGIS 网络分析[1] 介绍与博文目录【更新中】
  8. 快速找到ARP病毒源
  9. Coins、Tokens、山寨币:区别在哪里
  10. Aspose实现Office转PDF (ASP.NET)
  11. &quot;机器人防火墙&quot;:人机识别在应用安全及风控领域的一点实践
  12. LINUX监控-spotlight
  13. Hadoop记录- Yarn Job MAX
  14. Python虚拟环境笔记
  15. Spark学习之Spark安装
  16. zoj3820
  17. python中的字符串常量,是否支持通过下标的方式赋值
  18. Linux系统——防火墙
  19. angular.js 验证码注册登录
  20. H5唤起app

热门文章

  1. spring cloud: zuul(五): prefix访问前缀, ignoredServices粗粒度访问, yml不起作用
  2. java学习视频
  3. English trip V1 - 21. I dreamed dream Teacher:Corrine Key: past tense(过去式)
  4. laravel安装Excel安装不上
  5. git部署
  6. 2.1 uml序言
  7. python基础之字符串以及切片等操作
  8. 移动端自动化测试-Mac-IOS-Appium环境搭建
  9. 深拷贝的原生js实现
  10. vivado第一天从建立文件运行小程序开始