BZOJ1050. [HAOI2006]旅行comf(并查集,生成树)

2024-04-16 02:32

本文主要是介绍BZOJ1050. [HAOI2006]旅行comf(并查集,生成树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description
给你一个无向图,N(N<=500)个顶点, M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T,求
一条路径,使得路径上最大边和最小边的比值最小。如果S和T之间没有路径,输出”IMPOSSIBLE”,否则输出这个
比值,如果需要,表示成一个既约分数。 备注: 两个顶点之间可能有多条路径。
Input
第一行包含两个正整数,N和M。下来的M行每行包含三个正整数:x,y和v。表示景点x到景点y之间有一条双向公路
,车辆必须以速度v在该公路上行驶。最后一行包含两个正整数s,t,表示想知道从景点s到景点t最大最小速度比
最小的路径。s和t不可能相同。
1<N<=500,1<=x,y<=N,0<v<30000,0<M<=5000
Output
如果景点s到景点t没有路径,输出“IMPOSSIBLE”。否则输出一个数,表示最小的速度比。
如果需要,输出一个既约分数。
Sample Input
【样例输入1】
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3
Sample Output
【样例输出1】
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2
Hint
Source

思路: 暴力枚举加并查集

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>using namespace std;const int maxn = 5005;
const int INF = 0x3f3f3f3f;
int fa[maxn];struct Edge
{int x,y,w;bool operator<(const Edge&rhs)const{return w < rhs.w;}
}edges[maxn];int findset(int x)
{if(fa[x] == x)return x;return fa[x] = findset(fa[x]);
}int gcd(int n,int m)
{return m == 0 ? n : gcd(m,n % m);
}int main()
{int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++){scanf("%d%d%d",&edges[i].x,&edges[i].y,&edges[i].w);}sort(edges + 1,edges + 1 + m);int s,t;scanf("%d%d",&s,&t);int ans = 0;int mmin = 1,mmax = INF;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++)fa[j] = j;for(int j = i;j <= m;j++){int x = edges[j].x,y = edges[j].y;if(findset(x) != findset(y)){fa[findset(x)] = findset(y);}if(edges[j].w * mmin > mmax * edges[i].w)break;if(findset(s) == findset(t)){int tmp = gcd(edges[j].w,edges[i].w);mmax = edges[j].w / tmp;mmin = edges[i].w / tmp;break;}}}if(mmax == INF && mmin == 1){printf("IMPOSSIBLE\n");}else if(mmin == 1){printf("%d\n",mmax);}else printf("%d/%d\n",mmax,mmin);return 0;
}

这篇关于BZOJ1050. [HAOI2006]旅行comf(并查集,生成树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907583

相关文章

Python如何在Word中生成多种不同类型的图表

《Python如何在Word中生成多种不同类型的图表》Word文档中插入图表不仅能直观呈现数据,还能提升文档的可读性和专业性,本文将介绍如何使用Python在Word文档中创建和自定义各种图表,需要的... 目录在Word中创建柱形图在Word中创建条形图在Word中创建折线图在Word中创建饼图在Word

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-

Java实战之利用POI生成Excel图表

《Java实战之利用POI生成Excel图表》ApachePOI是Java生态中处理Office文档的核心工具,这篇文章主要为大家详细介绍了如何在Excel中创建折线图,柱状图,饼图等常见图表,需要的... 目录一、环境配置与依赖管理二、数据源准备与工作表构建三、图表生成核心步骤1. 折线图(Line Ch

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里,API

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log

Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南

《Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南》在日常数据处理工作中,我们经常需要将不同Excel文档中的数据整合到一个新的DataFrame中,以便进行进一步... 目录一、准备工作二、读取Excel文件三、数据叠加四、处理重复数据(可选)五、保存新DataFram

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成,并下载完全基于代码生成,并保存合并P

详解Java中如何使用JFreeChart生成甘特图

《详解Java中如何使用JFreeChart生成甘特图》甘特图是一种流行的项目管理工具,用于显示项目的进度和任务分配,在Java开发中,JFreeChart是一个强大的开源图表库,能够生成各种类型的图... 目录引言一、JFreeChart简介二、准备工作三、创建甘特图1. 定义数据集2. 创建甘特图3.