Nội dung Bài tập
- Mã:
- DSU_20201029_02
- Tên:
- Cây khung nhỏ nhất_Kruskal_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:
- 4301103017
Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G
Quảng cáo
Input Dòng 1: Chứa hai số n, m (1 <= n <= 10000; 1 <= m <= 15000) M dòng tiếp theo, dòng thứ i có dạng ba số nguyên u, v, c. Trong đó (u, v) là chỉ số hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó (1 <= u, v <= n; 0 <= c <= 10000).
Output: Gồm nhiều dòng mô tả các cạnh của cây khung, hiển thị các thông tin gồm đỉnh đầu, đỉnh cuổi, trọng sốVí dụ:
Input
Output
Input:
6 91 2 31 3 12 4 22 3 52 5 13 5 43 6 24 5 15 6 6
Output:
1 3 1
2 5 1
4 5 1
3 6 2
1 2 3
8
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;//Tự cho là gồm 4 chữ số , vì đề bài k n...