Hỏi đáp

Chia sẻ kiến thức, cùng nhau phát triển

ai giúp em bài này với ạ

11:44 03-09-2022 269 lượt xem 3 bình luận

Cho một cây (đơn đồ thị vô hướng không có chu trình) với các cạnh có trọng số. Trọng số của cây được định nghĩa bằng tổng trọng số các cạnh. Một cây con là cây thu được bằng cách xóa đi một số đỉnh ( và các cạnh có ít nhất một đỉnh bị xóa ).

Yêu cầu: Cho một cây, hãy tìm cây con có trọng số lớn nhất.

Dữ liệu: Vào từ file văn bản MAXTREE.INP

·      Dòng đầu ghi số N – số đỉnh của cây. ( 1 ≤ N ≤ 50000 )

·      N – 1 dòng sau, mỗi dòng ghi 3 số u, v, c thể hiện một cạnh của cây nối 2 đỉnh u, v, có trọng số là c. ( 1 ≤ u, v ≤ N, -10000 ≤ c ≤ 10000 )

Kết quả: Ghi ra file văn bản MAXTREE.OUT

·      Ghi ra một số duy nhất là trọng số lớn nhất có thể của một cây con.

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
THE SYLPH đã bình luận 12:09 03-09-2022

.

THE SYLPH đã bình luận 12:09 03-09-2022

.

.

.

THE SYLPH đã bình luận 12:09 03-09-2022

....................

 

Câu hỏi mới nhất