| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P146SUMI - ROUND 6I - Cây khung |
Cho một đồ thị vô hướng G gồm n đỉnh đánh số từ 1 tới n và không có cạnh nào. Người ta lần lượt thêm vào đồ thị m cạnh, cạnh thứ i nối hai đỉnh u_i, v_i và có trọng số là w_i. Trong quá trình thêm cạnh, giữa hai đỉnh có thể có nhiều cạnh nối.
Yêu cầu: Sau mỗi lệnh thêm cạnh, cho biết trọng số của cây khung nhỏ nhất của đồ thị G.
Input
Dòng đầu tiên chứa hai số nguyên dương n≤ 200, m ≤ 10^5.
m dòng tiếp, dòng thứ i chứa ba số nguyên u_i, v_i, w_i (|w_i| ≤ 10^9). Lưu ý trọng số cạnh có thể âm.
Output
Ghi ra m dòng, dòng thứ i ghi một số nguyên là trọng số cây khung nhỏ nhất của đồ thị G sau lệnh thêm cạnh thứ i, nếu sau lệnh thêm cạnh thứ i mà đồ thị không tồn tại cây khung, in ra 123456789.
Example
Input: 4 4
1 2 2
1 3 3
2 4 4
2 3 1 Output: 123456789
123456789
9
7
| Được gửi lên bởi: | adm |
| Ngày: | 2014-07-31 |
| Thời gian chạy: | 2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2019-09-05 10:44:01
cao nhân tốt bụng cho xin sol với :(( Last edit: 2019-09-05 10:44:53 |
|
|
2014-08-10 08:36:08 Tây Cuồng
AC... O(m * n) Last edit: 2014-10-17 16:16:57 |
