Nội dung Bài tập
- Mã:
- DSU_20201029
- Tên:
- Cây khung nhỏ nhất_Kruskal
- 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
- Nguồn bài tập:
- codeforces.com
- Link nguồn:
- https://codeforces.com/gr...
- Đượ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 1 dòng duy nhất: Ghi trọng số cây khung nhỏ nhất.Ví dụ:
Input
Output
Input:
6 91 2 31 3 52 4 22 3 22 5 13 5 43 6 34 5 45 6 2
Output mẫu
10
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 <iostream>using namespace std;struct ps { int tu, mau; &...