Đếm số lượng cây khung nhỏ nhất

Buổi 20 — Cây khung nhỏ nhất
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$
Draft saved