Thu thập tiền xu trong mê cung

General
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.

Draft saved