---
author: little
tags: MPATH
title: MPATH Solution
---

$\Huge\text{MPATH Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1xTesfgB5UdfmMNwpRbuFO3XUcFRr4xy5/view?usp=share_link)
📌 Tags: `dp` `graph` `dfs`
✍️ Writer: little
📋 Content:
[TOC]
:::

-----

## Thuật toán

Ta thấy vì các đỉnh được đánh số từ $0$ đến $10^9$ nên ta không thể dùng mảng thường để chứa được mà phải sử dụng đến cấu trúc dữ liệu $map$. Nhưng thực ra là ta không cần phải làm như vậy. Do là chỉ có $m$ cạnh nên ta chỉ quan tâm đến các đỉnh mà ta nhập vào lúc ban đầu thôi bởi vì các đỉnh khác không có cạnh nối thì sẽ có độ dài đường đi $MPATH$ là $1$, như vậy số đỉnh mà ta cần quan tâm tối đa sẽ là $2 * m$.

Đầu tiên, ta sẽ nén các tọa độ của các đỉnh ta vừa nhập vào từ $1$ đến $n$ ($n$ là số lượng đỉnh khác nhau trong các đỉnh mà ta vừa nhập).

Đến đây, bài toán sẽ trở thành: tìm đường đi $MPATH$ dài nhất của đồ thị gồm $n$ đỉnh và $m$ cạnh đã cho.

Gọi $dp[u]$ là độ dài đường đi $MPATH$ mà đỉnh bắt đầu là đỉnh $u$.

Ta chuyển trạng thái như sau: với các đỉnh $v$ là các đỉnh kề với đỉnh $u$, nếu như $v$ > $u$ thì ta sẽ cập nhật $dp[u]$ = $dp[u]$ + $max(dp[v])$.

Bởi vì đồ thị trong bài này có thể có khuyên. Nên khi mà đến một đỉnh nào đó có khuyên, thì ta sẽ luôn luôn ưu tiên đi vào cái khuyên đó. Như vậy sẽ luôn đưa ra kết quả tối ưu. Để giải quyết trường hợp có khuyên này, ta gọi mảng $res[u]$ là số lượng cạnh khuyên của đỉnh $u$. Thì khi xét đỉnh $u$, ta chỉ cần cộng $res[u]$ vào $dp[u]$ là được.

Độ phức tạp bài toán: $O(n * log(n))$
Việc tính mảng $dp$ chỉ mất $O(n)$ thôi, nhưng vì ta phải $sort$ và dùng $map$ để nén nên độ phức tạp sẽ trở thành $O(n * log(n))$.

----

Tham khảo code ở [đây](https://ideone.com/pJyUhS)