NGUỒN: Ôn HN tháng 11/2017, Thầy Nguyễn Đức Nghĩa, Ngày 1
Cho đồ thị có hướng với tập đỉnh gồm đỉnh và tập cung gồm cung. Các đỉnh của đồ thị được đánh số từ đến . Biết rằng đồ thị chứa hai đỉnh đặc biệt và : Từ có đường đi đến tất cả các đỉnh thuộc tập và từ các đỉnh luôn có đường đi đến . Cũng trên tập đỉnh ta có tập gồm cung. Mỗi cung được gán một số nguyên được gọi là trọng số của nó.
Vấn đề đặt ra là cần tìm cách bổ sung vào đồ thị một số cung từ tập sao cho:
Đồ thị thu được từ việc bổ sung các cung này vào đồ thị là đồ thị liên thông mạnh (nghĩa là luôn có đường đi nối hai đỉnh bất kỳ của đồ thị ).
Tổng trọng số của các cạnh bổ sung là nhỏ nhất.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên .
Dòng thứ hai chứa số nguyên không âm .
Tiếp đến là dòng, mỗi dòng mô tả một cung. Mỗi cung được xác định bởi đỉnh đầu và đỉnh cuối của nó.
Tiếp đến là số nguyên không âm .
Tiếp đến là dòng, mỗi dòng mô tả thông tin về một cung của tập gồm chỉ số đỉnh đầu, chỉ số đỉnh cuối và trọng số của cung. Trọng số của cung là số nguyên nằm trong khoảng từ đến . Giả thiết là .
Các số trên cùng dòng được ghi cách nhau bởi dấu cách.
Dữ liệu ra:
Dòng đầu tiên ghi YES nếu như có cách bổ sung các cung thỏa mãn yêu cầu đặt ra; ghi NO nếu trái ngược lại.
Nếu dòng đầu tiên là YES thì dòng thứ hai chứa số nguyên là tổng trọng số của các cạnh được bổ sung.
