Đồ thị
Đề bài
Mô tả
Cho một đồ thị gồm đỉnh và cung có hướng. Các đỉnh được đánh số từ đến , các cung được đánh số từ đến . Cung thứ đi từ đỉnh đến đỉnh và có chi phí .
Trong bài này, một đường đi hợp lệ là một dãy các cung trong đó cung đầu tiên xuất phát từ đỉnh , cung cuối cùng kết thúc tại đỉnh , và mỗi cung kết thúc tại đỉnh xuất phát của cung tiếp theo. Chính xác hơn, một đường đi hợp lệ được biểu diễn bởi dãy chỉ số thỏa mãn tất cả các điều kiện sau:
- ;
- ;
- ;
- với mọi thỏa mãn .
Lưu ý rằng các chỉ số này không nhất thiết phân biệt, nghĩa là một đường đi hợp lệ có thể đi qua một cung nhiều lần.
Nhiệm vụ của bạn là đánh dấu một số cung (có thể không cung nào hoặc tất cả các cung) là đặc biệt sao cho yêu cầu sau được thỏa mãn: mọi đường đi hợp lệ của đồ thị đều đi qua cung đặc biệt đúng một lần. Nói cách khác, nếu dãy chỉ số biểu diễn một đường đi hợp lệ thì có đúng một chỉ số () mà cung thứ được đánh dấu đặc biệt. Ngoài ra, tổng chi phí của các cung đặc biệt phải nhỏ nhất có thể.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test có dạng như sau:
- Dòng đầu tiên chứa hai số nguyên và (, ): số đỉnh và số cung của đồ thị.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên , , (, ): đỉnh xuất phát, đỉnh kết thúc và chi phí của cung thứ .
- Dòng cuối cùng là một dòng trống.
Dữ liệu vào kết thúc bằng hai số (không phải một bộ test). Dữ liệu đảm bảo:
- Với mọi cung, đỉnh xuất phát khác đỉnh kết thúc.
- Trong mỗi đồ thị, mỗi cặp có thứ tự xuất hiện nhiều nhất một lần.
- Luôn tồn tại một đường đi hợp lệ.
Tổng các giá trị của mọi bộ test không vượt quá . Tổng các giá trị của mọi bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in kết quả trên một dòng: nếu không thể đánh dấu các cung để thỏa mãn yêu cầu, in ra IMPOSSIBLE. Ngược lại, in ra tổng chi phí nhỏ nhất của các cung đặc biệt.
Ràng buộc
- , .
- , , ; các cặp trong một đồ thị đôi một khác nhau.
- Luôn tồn tại một đường đi hợp lệ.
- Tổng không vượt quá , tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 5 1 2 1 2 3 1 3 4 1 1 3 8 2 4 8 2 2 2 1 1 1 2 1 0 0 |
9 IMPOSSIBLE |
Ở bộ test thứ nhất có ba đường đi hợp lệ, với dãy chỉ số cung là , và . Cách tối ưu là đánh dấu cung thứ nhất và cung thứ tư. Đánh dấu cung thứ nhất và cung thứ ba là không hợp lệ vì đường đi đi qua cung đặc biệt hai lần. Ở bộ test thứ hai, đường đi hợp lệ có thể lặp lại cung: hay đều hợp lệ. Vì cung thứ hai xuất hiện nhiều lần trong các đường đi này nên không thể đánh dấu nó, do đó không có cách đánh dấu nào. |
| 3 3 1 2 5 2 1 2 2 3 4 3 3 1 2 3 2 3 1 3 2 1 0 0 |
4 3 |
Ví dụ bổ sung (không có trong đề gốc). Ở bộ test thứ nhất, đánh dấu cung : mọi đường đi hợp lệ có dạng và đi qua cung này đúng một lần. Ở bộ test thứ hai, không thể đánh dấu cung vì đường đi đi qua nó hai lần; đánh dấu cung với chi phí . |
Bình luận