Đường đi giá trị nhất qua thành phần mạnh
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị có hướng gồm $N$ đỉnh và $M$ cạnh. Mỗi đỉnh $i$ có một lượng vàng $c_i \ge 0$. Bạn có thể xuất phát từ một đỉnh bất kỳ và đi theo các cạnh có hướng qua nhiều đỉnh tùy ý (có thể đi qua một đỉnh hoặc cạnh nhiều lần, nhưng vàng tại mỗi đỉnh chỉ được nhặt tối đa một lần).
Hãy tìm tổng lượng vàng lớn nhất có thể thu thập được trên một lộ trình hợp lệ.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $c_1, c_2, \dots, c_N$ ($0 \le c_i \le 10^9$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh có hướng từ $u$ đến $v$.
Dữ liệu ra
- Một số nguyên duy nhất là tổng lượng vàng lớn nhất có thể thu thập.
Ví dụ
| Input | Output |
|---|---|
| 4 4 4 5 2 7 1 2 2 1 2 3 3 4 |
18 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $0 \le c_i \le 10^9$
Community Discussion