Khôi Phục Giá Trị Cảm Biến Qua Tổng Cặp Đồ Thị

Buổi 63 — Interactive & Constructive Graphs
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một mạng gồm $N$ cảm biến (đánh số từ $1$ đến $N$) đang lưu trữ các giá trị nguyên không âm bí mật $a_1, a_2, \dots, a_N \ge 0$. Hệ thống thực hiện $M$ phép đo tương tác; phép đo thứ $i$ trả về tổng giá trị của cặp cảm biến $(u_i, v_i)$: $a_{u_i} + a_{v_i} = s_i$.

Hãy kiểm tra xem có tồn tại bộ giá trị nguyên không âm $(a_1, a_2, \dots, a_N)$ thỏa mãn tất cả $M$ phép đo hay không. Nếu có, hãy tìm tổng $\sum_{i=1}^{N} a_i$ nhỏ nhất có thể; ngược lại in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, s_i$ ($1 \le u_i, v_i \le N$, $0 \le s_i \le 10^9$).
Dữ liệu ra

In ra tổng $\sum_{i=1}^{N} a_i$ nhỏ nhất có thể, hoặc -1 nếu các phép đo mâu thuẫn.

Ví dụ
Input Output
4 3
1 2 5
2 3 7
3 4 6
11
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved