Xưởng Chế Tạo Phép Thuật
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị có hướng gồm N đỉnh và M cạnh, mỗi đỉnh i có giá trị w[i]. Xây dựng đồ thị rút gọn. Trọng số mỗi đỉnh trong DAG rút gọn bằng tổng giá trị của các đỉnh trong SCC tương ứng.
Hãy tìm một đỉnh s (trong đồ thị gốc) sao cho tổng giá trị của tất cả các đỉnh mà s có thể đến được là lớn nhất. In tổng giá trị lớn nhất đó.
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
- Dòng thứ hai: N số nguyên w[1], w[2], ..., w[N] (1 ≤ w[i] ≤ 10^9)
- M dòng tiếp theo: u v
Dữ liệu ra
- Một số nguyên: tổng giá trị lớn nhất có thể thu được.
Ví dụ
| Input | Output |
|---|---|
| 5 5\n10 20 30 40 50\n1 2\n2 3\n3 1\n3 4\n4 5 | 150 |
Giới hạn
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
- 1 ≤ w[i] ≤ 10^9
Community Discussion