Đếm số lượng cây khung nhỏ nhất
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh và $M$ cạnh. Hai cây khung được coi là khác nhau nếu tập các chỉ số cạnh được chọn khác nhau.
Hãy đếm số lượng cây khung nhỏ nhất (MST) khác nhau của đồ thị theo modulo $10^9 + 7$. Nếu đồ thị không liên thông, in ra 0.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 100, 0 \le M \le 1000$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
Dữ liệu ra
- In ra số lượng MST theo modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 1 2 3 1 3 4 1 1 4 1 1 3 1 |
8 |
| 3 3 1 2 1 2 3 2 1 3 3 |
1 |
Giới hạn
- $1 \le N \le 100$
- $0 \le M \le 1000$
- $1 \le w_i \le 10^9$
Community Discussion