Cây Khung Nhỏ Nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho đồ thị vô hướng liên thông $N$ đỉnh, $M$ cạnh có trọng số. Mỗi giá trị trọng số xuất hiện tối đa 3 lần.

Hãy tìm:

Dòng 1: Hai số nguyên $N$ và $M$
$M$ dòng tiếp theo: Ba số nguyên $A_{i}, B_{i}, W_{i}$ — cạnh nối $A_{i}$ với $B_{i}$ có trọng số $W_{i}$

Một dòng chứa hai số: tổng trọng số MST và số MST khác nhau (mod $10^{9} + 7$ ).

Input	Output	Giải thích
4 5 1 2 1 3 4 1 1 3 2 1 4 2 2 3 2	4 3	MST có tổng = 4. Có 3 MST khác nhau (chọn 2 cạnh trọng số 1 + 1 cạnh trọng số 2)

Bình luận

Không có bình luận tại thời điểm này.