Thu thập xu trên đồ thị nén
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một đồ thị có hướng bất kỳ (có thể chứa chu trình) gồm $N$ đỉnh và $M$ cạnh có hướng. Mỗi đỉnh $i$ có $a_i$ đồng xu. Bạn có thể chọn bất kỳ đỉnh nào để xuất phát, di chuyển theo các cạnh có hướng và dừng lại ở bất kỳ đỉnh nào. Bạn có thể đi qua một đỉnh nhiều lần, nhưng số xu tại mỗi đỉnh chỉ được thu thập tối đa một lần. 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$.
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
- $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
- In ra tổng số xu lớn nhất có thể thu thập.
Ví dụ
| Input | Output |
|---|---|
| 4 4\n4 5 2 7\n1 2\n2 1\n1 3\n2 4 | 16 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
- $1 \le a_i \le 10^9$
Community Discussion