Lập trình đơn giản - Hỏi đáp

Người hay giúp bạn khác trả lời bài tập sẽ trở thành học sinh giỏi. Người hay hỏi bài thì không. Còn bạn thì sao?

Xây dựng đường đua Thành phố ACM quyết định tổ chức một cuộc đua xe hậu Valentine. Thành phố gồm n nút giao thông và không có con đường nào nối 2 nút giao thông bất kỳ. Vì vậy ban tổ chức (BTC) muốn xây dựng các đường đua nối các nút giao thông lại với nhau tạo thành các vòng đua. Sau khi tham khảo giá cả từ công ty MCA, BTC đưa ra một danh sách gồm m con đường một chiều nối giữa 2 nút giao thông có thể xây dựng và giá của chúng. Vì muốn xây dựng thật nhiều vòng đua (như vậy sẽ có nhiều cuộc đua diễn ra song song), BTC muốn tất cả các nút giao thông đều được sử dụng trong cuộc đua và mỗi nút giao thông chỉ thuộc đúng một vòng đua (nghĩa là từ một nút giao thông chỉ có thể di chuyển tới các nút giao thông khác thuộc cùng một vòng đua). Chi phí xây dựng cuộc đua là tổng chi phí xây dựng các vòng đua, trong đó chi phí xây dựng một vòng đua là tổng chi phí xây dựng các đường đua thuộc vòng đua đó. Các NTUCoders hãy giúp BTC chọn các con đường cần xây dựng sao cho tổng chi phí là bé nhất nhé!

Chú ý: Các nút giao thông x1, x2, x3, ..., xk tạo thành một vòng đua nếu như ta có đường đi xi -> xi+1 -> xi+2 -> ... -> xi (1 <= i <= k).

Dữ liệu vào

Dòng thứ nhất chứa 2 số nguyên dương n và m

m dòng tiếp theo, dòng thứ i gồm 3 số u, v, w với ý nghĩa có thể xây dựng con đường nối từ u đến v với giá là w

Dữ liệu ra

In ra tổng chi phí bé nhất tìm được hoặc in ra -1 nếu không có cách xây dựng thỏa mãn yêu cầu bài toán

Giới hạn

1 <= n <= 500, 1 <= m <= n*(n-1)

1 <= w <= 109

Dữ liệu đảm bảo không có đường đua nào nối một nút giao thông với chính nó

Ví dụ

Input

6 8
1 2 3
2 3 2
3 1 6
2 4 3
4 6 1
6 5 2
5 4 3
5 3 4

Output

17

Giải thích: xây dựng các đường đua tạo thành 2 vòng đua: 1 -> 2 -> 3 và 4 -> 6 -> 5 với chi phí là 17

0 câu trả lời
Click để xem thêm, còn nhiều lắm! Gửi câu hỏi

...

Dưới đây là những câu hỏi có bài toán hay do Hoc24 lựa chọn.

Building.