Domino trên đồ thị
Đề bài
Mô tả
Cho một bộ quân domino. Với mỗi cặp thỏa , có đúng một quân domino mà một nửa chứa chấm và nửa còn lại chứa chấm. Như vậy bộ có đúng quân.
Cho một đồ thị vô hướng không có khuyên và không có cạnh lặp. Bạn muốn đặt một số quân domino lên các cạnh của đồ thị, mỗi loại quân domino dùng nhiều nhất một lần, và mỗi cạnh đặt nhiều nhất một quân. Không bắt buộc phải đặt domino lên mọi cạnh.
Khi đặt một quân domino lên một cạnh, bạn chọn hướng cho nó: một nửa quay về một đầu mút, nửa kia quay về đầu mút còn lại. Ràng buộc: nếu có nhiều nửa quân domino cùng quay về một đỉnh, thì tất cả các nửa đó phải có cùng số chấm.
Hỏi nhiều nhất có thể đặt được bao nhiêu quân domino lên các cạnh của đồ thị?
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và : số đỉnh và số cạnh của đồ thị.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và cho biết có một cạnh nối đỉnh và đỉnh .
Đồ thị có thể không liên thông, nhưng đảm bảo không có khuyên và giữa mỗi cặp đỉnh có nhiều nhất một cạnh.
Dữ liệu ra
In ra một số nguyên: số quân domino nhiều nhất có thể đặt được.
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 1 2 2 3 3 4 4 1 |
4 | Gán cho mỗi đỉnh một số chấm sao cho mọi nửa quay về cùng một đỉnh có cùng số chấm; ở đây đặt được domino lên cả cạnh với quân khác nhau. |
| 3 1 1 3 |
1 | Chỉ có một cạnh nên nhiều nhất đặt được một quân. |
| 7 0 | 0 | Đồ thị không có cạnh nên không đặt được quân nào. |
| 7 21 1 2 1 3 1 4 1 5 1 6 1 7 2 3 2 4 2 5 2 6 2 7 3 4 3 5 3 6 3 7 4 5 4 6 4 7 5 6 5 7 6 7 |
16 | Đồ thị đầy đủ đỉnh; với giá trị chấm không thể phủ hết cạnh bằng các quân khác nhau, tối đa là . |
Bình luận