如何通过Kruscal算法在hdu1598问题中实现枚举求解？

本文共计1010个文字，预计阅读时间需要5分钟。

题目：寻找最舒适的路线

时间限制：1000MS

内存限制：32768KB

描述：给定一个地图，每个点代表一个地点，每条边代表一条道路。道路有舒适度之分，现在需要找到一条路径，使得从起点到终点的总舒适度最高。

输入：第一行包含两个整数N和M，分别表示地图上的地点数量和道路数量。接下来N行，每行包含一个地点的坐标。接下来M行，每行包含两个整数a和b，表示地点a和地点b之间有一条道路。

输出：输出一个整数，表示从起点到终点的最大舒适度。如果不存在路径，输出-1。

acm.hdu.edu.cn/showproblem.php?pid1598

find the most comfortable road

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10307    Accepted Submission(s): 4289  

Problem Description

XX星有许多城市城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构进行交流每条SARS都对行驶在上面的Flycar限制了固定的Speed同时XX星人对 Flycar的“舒适度”有特殊要求即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求flycar必须瞬间提速/降速痛苦呀 ), 但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的。