Đếm Cây Khung Nhỏ Nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Có một lưới $N \times K$ ô. Mỗi cặp ô kề nhau (theo hàng hoặc cột) được ngăn cách bởi một cửa có chi phí mở. Bạn cần chọn một tập cửa tối thiểu để tất cả $N \times K$ ô thông nhau (cây khung nhỏ nhất). Hãy đếm số cách chọn tập cửa đó (số cây khung nhỏ nhất khác nhau), lấy kết quả modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ , $K$ ( $2 \leq N \leq 30000$ , $2 \leq K \leq 6$ )
$N$ dòng tiếp theo, mỗi dòng $K - 1$ số nguyên: chi phí cửa ngang trong hàng đó (từ trái sang phải)
$K$ dòng tiếp theo, mỗi dòng $N - 1$ số nguyên: chi phí cửa dọc trong cột đó (từ trên xuống)

Dữ liệu ra

Số cây khung nhỏ nhất, modulo $10^{9} + 7$ .

Ràng buộc

$2 \leq N \leq 30000$ , $2 \leq K \leq 6$
Chi phí cửa: $1 \leq w \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1	10	Cây khung nhỏ nhất dùng 9 trong 10 cạnh trọng số 1 và thêm 2 cạnh trọng số 2,3. Có đúng 10 cách chọn cạnh trọng số 1 nào bị bỏ qua.

Bình luận

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