Khôi Phục Cây Từ Ma Trận Khoảng Cách
Đề bài
Một hệ thống ẩn giấu một cây có trọng số gồm $N$ đỉnh (đánh số từ $1$ đến $N$) với trọng số các cạnh là các số nguyên dương. Sau quá trình thăm dò tương tác khoảng cách giữa mọi cặp đỉnh, bạn thu được ma trận $D$ kích thước $N \times N$, trong đó $D_{i, j}$ là tổng trọng số trên đường đi duy nhất giữa đỉnh $i$ và đỉnh $j$.
Hãy kiểm tra xem ma trận $D$ có thể được sinh ra từ một cây có trọng số nguyên dương hợp lệ hay không. Nếu có, hãy khôi phục và in ra $N - 1$ cạnh của cây đó (mỗi cạnh gồm $u, v, w$ với $u < v$, sắp xếp tăng dần theo thứ tự từ điển $(u, v)$); ngược lại in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 40$).
- $N$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên $D_{i, j}$ ($0 \le D_{i, j} \le 10^{12}$).
Dữ liệu ra
Nếu tồn tại cây hợp lệ, in ra $N - 1$ dòng, mỗi dòng gồm ba số nguyên $u, v, w$ ($u < v, w > 0$) được sắp xếp tăng dần theo $(u, v)$. Nếu ma trận không hợp lệ, in ra -1.
Ví dụ
| Input | Output |
|---|---|
| 4 0 3 8 5 3 0 5 2 8 5 0 7 5 2 7 0 |
1 2 3 2 3 5 2 4 2 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion