---
author: nguyencter
tags: Speed
title: Speed Solution
---

$\Huge\text{Speed Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1Avf1-ddrJhpUP830XoK4gzXm3gOvAB55/view?usp=sharing)
📌 Tags: `kruskal` `brute force`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

Một thành phố du lịch có $n$ địa điểm được kết nối với nhau bằng $m$ con đường hai chiều. Con đường thứ $k$ ($1≤ k ≤ m$) kết nối địa điểm $i_k$ với $j_k$ và cho các phương tiện đi với tốc độ đúng bằng $s_k$

Để khuyến khích khách du lịch đi lại an toàn trong thành phố, lãnh đạo thành phố muốn xác định giá trị $min_s$ và $max_s$ tương ứng là tốc độ tối thiểu và tốc độ tối đa để khi một phương tiện duy trì vận tốc trong đoạn từ $min_s$ đến $max_s$ thì có thể đi đến tất cả thành phố xuất phát từ một bất kì thành phố.

**Yêu cầu:** Tìm giá trị $min_s$ và $max_s$ thỏa mãn điều kiện $max_s-min_s$ đạt giá trị nhỏ nhất, nếu có nhiều bộ $min_s$ và $max_s$ thỏa mãn, cần tìm bộ mà $min_s$ nhỏ nhất.

-----

## Thuật toán

Vì số cạnh là $m ≤ 10000$ nên ta có thể duyệt qua từng cây khung để tìm kết quả tối ưu nhất.

Sắp xếp lại $m$ cạnh theo giá trị tăng dần của $s$.

Duyệt qua $m$ cạnh:
- Với mỗi cạnh ta lại tìm xem có thể tạo được cây khung chỉ với số cạnh từ $i$ đến $m$ hay không.
- Nếu có thì ta chỉ cần lưu lại kết quả tối ưu là $max_s-min_s$ có giá trị nhỏ nhất.
- Ngược lại thì thoát khỏi vòng lặp.

Độ phức tạp là $O(m^2)$.

----
Tham khảo code mẫu ở [đây](https://github.com/nguyencter/CODE/blob/main/speed.cpp).