P2502 [HAOI2006]旅行

一定要看清题目数据范围再决定用什么算法,我只看着是一个蓝题就想到了记录最短路径+最小生成树,但是我被绕进去了;

看到只有5000的边,我们完全可以枚举最小边和最大边,判断起点和终点是否连通用并查集维护一下就好了;

分数约分一定要仔细想想,

an1==ans2的时候我直接printf("%d",ans1)了,(劝退到小学)

gcd自己写一个吧,(图省事用__gcd()在洛谷水一水也不是不可以吧)

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct node
{
int x,y,z; bool operator < (const node &we)const
{
return z<we.z;
}
}f[maxn]; int n,m; int father[maxn]; int getfather(int x)
{
if(father[x]==x) return x;
father[x]=getfather(father[x]);
return father[x];
} void merging(int x,int y)
{
father[getfather(x)]=getfather(y);
} int s,t; double ans=1e9; int ans1,ans2; int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) father[i]=i;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);
merging(f[i].x,f[i].y);
} scanf("%d%d",&s,&t); if(getfather(s)!=getfather(t))
{
printf("IMPOSSIBLE\n");
return ;
}
sort(f+,f+m+);
for(int i=;i<=m;i++)
{
for(int k=;k<=n;k++) father[k]=k;
for(int j=i;j<=m;j++)
{
merging(f[j].x,f[j].y);
if(getfather(s)==getfather(t))
{
double qw=(double)f[j].z/(double)f[i].z;
if(qw<ans)
{
ans=qw;
ans1=f[j].z;ans2=f[i].z;
}
break;
}
}
} if(ans1==ans2)
{
printf("");
}
else
{
int we=gcd(ans1,ans2);
if(ans2/we==) printf("%d",ans1/we);
else printf("%d/%d\n",ans1/we,ans2/we);
}
return ;
}

最新文章

  1. 文本框focus之后高亮背景颜色
  2. 选择QT作为自己的图形库
  3. 转-servlet 获取 post body 体用流读取为空的问题
  4. 当div自适应的高度超过预设的高度的时候出现滚动条的办法
  5. MyBatis之传入参数
  6. ctrl+shift+del 清理火狐缓存,解决页面显示错乱问题
  7. 三分--Football Goal(面积最大)
  8. iOS-Core-Animation-Advanced-Techniques(一)
  9. gVim编辑器 操作篇
  10. 【English】20190308
  11. 【Gym - 101124A】The Baguette Master (数学,几何)
  12. 4.2计算字符的ASCII碼
  13. HDU 6090 17多校5 Rikka with Graph(思维简单题)
  14. 使用blessed 开发丰富的cli 应用
  15. 队列(链式队列)----C语言
  16. C++ 文本查询2.0(逻辑查询)
  17. SQL----&gt;数据库表设计思想
  18. python 面向对象 isinstance
  19. Nginx 内嵌lua脚本,结合Redis使用
  20. JUnit4.12 源码分析之Statement

热门文章

  1. 规格化设计——OO第三单元总结
  2. 前端js入门之 JavaScript 对象直接量
  3. SQLSEVER导出 xml文件
  4. JVM参数优化(基础篇)
  5. Web前端面试图
  6. 第三天Beta冲刺
  7. Union-Find(并查集): Dynamic Connectivity 问题
  8. .net框架 - Enum枚举
  9. used to do 与be used to doing /n.
  10. 关于List集合中元素排序问题