Nội dung Bài tập
- Mã:
- [DHLTNC_N8]_DSU_02
- Tên:
- DHLTNC_N8_Bài 02
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4801103029
Đề: Cho một đồ thị vô hướng gồm n đỉnh và m cạnh
có trọng số.
Quảng cáo
Hãy tìm tổng trọng số nhỏ nhất của cây khung nhỏ nhất (Minimum Spanning Tree - MST) của đồ thị.
Cây khung nhỏ nhất là một tập hợp các cạnh kết nối tất cả các đỉnh của đồ thị mà không có chu trình và có tổng trọng số nhỏ nhất.
Yêu cầu: Sử dụng cấu trúc DSU.
Input:
· Dòng đầu tiên: 2 số nguyên n và m — số lượng đỉnh và số lượng cạnh.
· m dòng tiếp theo: mỗi dòng gồm 3 số nguyên u, v, w:
o u và v: hai đỉnh nối bởi cạnh
o w: trọng số của cạnh đó
Output:
· Một số nguyên duy nhất là tổng trọng số của cây khung nhỏ nhất.
|
Input |
Output |
|
4 5 0 1 1 0 2 3 1 2 2 1 3 4 2 3 5 |
7 |
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
#include <stdio.h>void gcd (int a , int b) { int ucln = 1; ...