Đồ thị nhỏ nhất của cây khung

View as PDF

Submit solution

Points: 0.60 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Chuẩn bị đề bài cho các kỳ thi là một công việc vô cùng khó khăn. Dù được chuẩn bị kĩ càng đến đâu, đề bài sẽ luôn có những chỗ khó hiểu, bug trong lời giải mẫu, lỗi sai trong input / output...

Trong bài này, các bạn sẽ vào vai người ra đề. Bạn nhận phụ trách một bài toán vô cùng đơn giản như sau: "Cho một đồ thị vô hướng. Tìm cây khung nhỏ nhất."

Hầu hết tất cả công việc đã được chuẩn bị xong: Đề bài với cốt truyện vô cùng dài dòng, khó hiểu và không cần thiết, lời giải mẫu đơn giản, và cả output. Thứ duy nhất còn thiếu là input.

Vấn đề là với một đồ thị, có thể có nhiều cây khung khác nhau. Tuy nhiên bạn lại quá lười để viết một trình chấm. Vì vậy bạn cần tìm một đồ thị mà cây khung nhỏ nhất là duy nhất.

Hơn nữa, bạn muốn bộ test của bạn phải 'khó'. Ví dụ, nếu các cạnh ngoài cây khung có trọng số lớn hơn nhiều so với các cạnh trong cây khung, một thuật toán tham vớ vẩn sẽ có thể ăn hết bộ test. Vì vậy, bạn muốn sinh một đồ thị đầy đủ, với tổng trọng số của các cạnh của đồ thị là nhỏ nhất.

Input

  • Dòng 1: ~N~ - số đỉnh của cây khung ~(N \le 50,000~)

  • ~N-1~ dòng tiếp theo, mỗi dòng 3 số nguyên ~u~, ~v~, ~c~, thể hiện có một cạnh nối giữa 2 đỉnh ~u~ ~v~ với trọng số ~c~. ~(1 \le u, v \le N; c \le 10^9)~

Output

Một số nguyên duy nhất là tổng trọng số nhỏ nhất của đồ thị, mà cây khung trong input là cây khung nhỏ nhất duy nhất.

Sample Input 1

4
1 2 1
1 3 1
1 4 2

Sample Output 1

12

Sample Input 2

3
1 2 5
2 3 5

Sample Output 2

16

Comments

Please read the guidelines before commenting.


There are no comments at the moment.