{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Xem xét bài toán chọn một tập hợp T các đường truyền tốc độ cao để kết nối N điểm máy tính, từ một tập hợp gồm M đường truyền tốc độ cao, mỗi đường nối một cặp điểm máy tính. Mỗi đường truyền tốc độ cao có một chi phí hàng tháng nhất định, và mục tiêu là giảm thiểu tổng chi phí kết nối N điểm máy tính, nơi tổng chi phí là tổng của chi phí của mỗi đường dây được bao gồm trong tập hợp T. Xem xét thêm rằng bài toán này đã được giải quyết trước đây cho tập hợp N điểm máy tính và M đường truyền tốc độ cao, nhưng gần đây có thêm K đường truyền tốc độ cao mới đã trở nên khả dụng.\nMục tiêu của bạn là tính toán tập hợp T\u0027 mới có thể mang lại chi phí thấp hơn so với tập hợp T gốc, do có thêm K đường truyền tốc độ cao mới và khi có M + K đường truyền tốc độ cao khả dụng.\n### Đầu vào\nĐầu vào sẽ chứa nhiều trường hợp kiểm tra, mỗi trường hợp được mô tả như dưới đây. Các trường hợp kiểm tra liên tiếp được tách biệt bởi một dòng trắng.\nĐầu vào được tổ chức như sau:\n- Một dòng chứa số N của các điểm máy tính, với 1 \u003c N \u003c 1000000, và mỗi điểm máy tính được tham chiếu bởi một số i, 1 \u003c i \u003c N.\n- Tập hợp T của các đường truyền tốc độ cao đã chọn trước đó, bao gồm N - 1 đường, mỗi đường mô tả một đường truyền tốc độ cao, và chứa số của hai điểm máy tính mà đường dây kết nối và chi phí hàng tháng của việc sử dụng đường dây này. Tất cả các chi phí đều là số nguyên.\n- Một dòng chứa số K của các đường mới thêm, 1 \u003c K \u003c 10.\n- K dòng, mỗi dòng mô tả một đường truyền tốc độ cao mới, và chứa số của hai điểm máy tính mà đường dây kết nối và chi phí hàng tháng của việc sử dụng đường dây này. Tất cả các chi phí đều là số nguyên.\n- Một dòng chứa số M của các đường truyền tốc độ cao ban đầu có sẵn, với N - 1 \u003c M \u003c N(N - 1)/2.\n- M dòng, mỗi dòng mô tả một trong các đường truyền tốc độ cao ban đầu có sẵn, và chứa số của hai điểm máy tính mà đường dây kết nối và chi phí hàng tháng của việc sử dụng đường dây này. Tất cả các chi phí đều là số nguyên.\n\n### Đầu ra\nĐối với mỗi trường hợp kiểm tra, đầu ra phải tuân theo mô tả dưới đây. Các đầu ra của hai trường hợp liên tiếp sẽ được tách biệt bởi một dòng trắng.\nTệp đầu ra phải có một dòng chứa chi phí gốc của việc kết nối N điểm máy tính với M đường truyền tốc độ cao và một dòng khác chứa chi phí mới của việc kết nối N điểm máy tính với M + K đường truyền tốc độ cao. Nếu chi phí mới bằng với chi phí gốc, giá trị tương tự được viết hai lần.\n\n### Ví dụ \n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n12 5\n13 5\n14 5\n15 5\n1\n232\n6\n125\n135\n145\n155\n3 4 8\n4 5 8\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e20\n17\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}