Khôi Phục Giá Trị Cảm Biến Qua Tổng Cặp Đồ Thị
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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.
Community Discussion