| Submit | All submissions | Best solutions | Back to list |
EIUEASKRU - Cây khung |
Cho dữ liệu mô tả đồ thị vô hướng với cạnh có trọng số. Hãy viết chương trình tìm thành phần liên thông mà có cây khung nhỏ nhất (MST) của nó có tổng trọng số lớn nhất.
Input
Dòng đầu tiên gồm 2 số nguyên N, M (N, M ≤ 3*105) tương ứng là số đỉnh và số cạnh của đồ thị.
Dòng thứ i trong M dòng tiếp theo gồm hai số 3 số nguyên ui, vi, wi cho biết cạnh nối ui và vi có trọng số wi (1 ≤ ui, vi ≤ N, 0 ≤ wi ≤ 109).
Output
In ra tổng trọng số lớn nhất trong các MST có trong đồ thị.
Example
Input: 5 4 1 2 4 1 3 1 2 3 3 4 5 5 Output: 5 Input: 5 4 1 2 4 1 3 2 2 3 3 4 5 4 Output: 5
| Added by: | Ha Minh Ngoc |
| Date: | 2017-12-10 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG FSHARP GO JAVA JS-MONKEY NODEJS PHP PYTHON PYPY PYPY3 PYTHON3 RUBY SQLITE SWIFT VB.NET |
RSS