Xưởng Chế Tạo Phép Thuật

Buổi 43 — SCC (Tarjan) & 2-SAT Dynamic Programming
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved