P2502 [HAOI2006]旅行——暴力和并查集的完美结合
2024-09-26 01:30:32
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 ;
}
最新文章
- 文本框focus之后高亮背景颜色
- 选择QT作为自己的图形库
- 转-servlet 获取 post body 体用流读取为空的问题
- 当div自适应的高度超过预设的高度的时候出现滚动条的办法
- MyBatis之传入参数
- ctrl+shift+del 清理火狐缓存,解决页面显示错乱问题
- 三分--Football Goal(面积最大)
- iOS-Core-Animation-Advanced-Techniques(一)
- gVim编辑器 操作篇
- 【English】20190308
- 【Gym - 101124A】The Baguette Master (数学,几何)
- 4.2计算字符的ASCII碼
- HDU 6090 17多校5 Rikka with Graph(思维简单题)
- 使用blessed 开发丰富的cli 应用
- 队列(链式队列)----C语言
- C++ 文本查询2.0(逻辑查询)
- SQL---->;数据库表设计思想
- python 面向对象 isinstance
- Nginx 内嵌lua脚本,结合Redis使用
- JUnit4.12 源码分析之Statement