1050: [HAOI2006]旅行comf(枚举最小生成树)

2024-03-09 05:48

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

1050: [HAOI2006]旅行comf

https://www.lydsy.com/JudgeOnline/problem.php?id=1050

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4538  Solved: 2576
[Submit][Status][Discuss]

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

 思路:把边按权值从小到大排序,

            枚举所有的最小值。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio> 
using namespace std;
struct EDGE{int u,v;int val;
}eg[5009];
int father[509];
int find( int x ){return father[x] == x ? father[x] :father[x] = find(father[x]); 
}
int cmp( struct EDGE a , struct EDGE b){return a.val < b.val;
}
int gcd( int a ,int b ){return b ? gcd(b,a%b) : a; 
} 
int main(void){int n,m;int cnt=0;scanf("%d %d",&n,&m);for( int i=0;i<m;i++) scanf("%d %d %d",&eg[i].u,&eg[i].v,&eg[i].val);int s,t;scanf("%d %d",&s,&t);    sort(eg,eg+m,cmp);int flag=0;int ansmaxx = 999999;int ansminn = 1;for( int j=0;j<m;j++){ int f=0;int maxx = -1;int minn =999999;for( int k=1;k<=n;k++)father[k] = k;for( int i=j;i<m;i++){int x  = eg[i].u;int y  = eg[i].v;int fx = find( x );int fy = find( y );if(  fx!= fy ){father[fx] = fy;maxx = max( eg[i].val,maxx);minn = min( eg[i].val,minn);if( find(s) ==find(t) ){f=1;flag = 1;if( ( double)(( double)ansmaxx / ( double)ansminn ) > (double)(( double)maxx / ( double)minn)){ansmaxx = maxx;ansminn = minn;}break;}}}if( f==0 )break;}if( flag==0 )printf("IMPOSSIBLE\n");else if( ansmaxx % ansminn == 0 )printf("%d\n",ansmaxx/ansminn);else{int g = gcd(ansmaxx,ansminn);printf("%d/%d\n",ansmaxx/g, ansminn/g);}return 0;
}

 

这篇关于1050: [HAOI2006]旅行comf(枚举最小生成树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

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