Thu thập xu trên đồ thị có hướng
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một trò chơi gồm $n$ phòng và $m$ đường hầm một chiều nối giữa các phòng. Trong phòng thứ $i$ có $k_i$ đồng xu. Bạn có thể bắt đầu tại một phòng bất kỳ, di chuyển qua các đường hầm tùy ý (có thể đi qua một phòng nhiều lần, nhưng số xu trong mỗi phòng chỉ được thu thập tối đa một lần), và kết thúc tại một phòng bất kỳ. Hãy tìm tổng số xu lớn nhất có thể thu thập được.
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 $k_1, k_2, \dots, k_n$ ($1 \le k_i \le 10^9$).
- $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả đường hầm một chiều từ $u$ đến $v$.
Dữ liệu ra
- Một số nguyên duy nhất là tổng số xu lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 4 4 5 2 7 1 2 2 1 1 3 2 4 |
16 |
Giới hạn
- $1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5$
Community Discussion