Thu thập tiền xu trong mê cung
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một trò chơi có $N$ căn phòng và $M$ hành lang một chiều. Trong phòng thứ $i$ có $c_i$ đồng xu. Người chơi có thể bắt đầu tại một phòng bất kỳ, đi qua các hành lang một chiều và dừng lại ở bất kỳ phòng nào. Có thể đi qua một phòng nhiều lần nhưng tiền xu tại mỗi phòng chỉ được thu thập tối đa một lần.
Hãy tìm tổng số tiền xu lớn nhất có thể thu thập.
Dữ liệu vào
- Dòng đầu 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ố $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
In ra tổng số tiền xu lớn nhất có thể thu thập.
Ví dụ
| Input | Output |
|---|---|
| 4 4 4 5 2 7 1 2 2 1 1 3 2 4 |
16 |
| 3 0 10 25 15 |
25 |
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