Khôi Phục Cây Từ Ma Trận Khoảng Cách

Buổi 63 — Interactive & Constructive Graphs Trees
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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.

Draft saved