UVa 11080 Place the Guards
Đề: 11080 Place the Guards
Abridge: Có v (vertices) junction (giao lộ) và e (edges) streets (con đường). Một Guard (bảo vệ) đặt tại mỗi vertex (giao lộ) sẽ bảo vệ các junctions và street cận kề. Nếu 2 guards cùng bảo vệ 1 con đường sẽ gây ra đánh nhau. Tìm số bảo vệ ít nhất để bảo vệ tất cả con đường và giao lộ sao cho không xảy ra xung đột.
Solution: Bipartite Graph Check + numCC
Vì Graph có nhiều connected component nên:
* Lưu ý: Khi CC chỉ có 1 vertex thì 1 TH duy nhất là phải color nó = 1 (guard here)
Code:
Abridge: Có v (vertices) junction (giao lộ) và e (edges) streets (con đường). Một Guard (bảo vệ) đặt tại mỗi vertex (giao lộ) sẽ bảo vệ các junctions và street cận kề. Nếu 2 guards cùng bảo vệ 1 con đường sẽ gây ra đánh nhau. Tìm số bảo vệ ít nhất để bảo vệ tất cả con đường và giao lộ sao cho không xảy ra xung đột.
Solution: Bipartite Graph Check + numCC
Vì Graph có nhiều connected component nên:
- Các CC độc lập với nhau.
- Với mỗi CC ta lần lượt color vertex đầu = 0 (no guard) hoặc 1 (guards here), nếu cả 2 trường hợp đều return -1 (mâu thuận or ko cover) thì printf("-1"), còn nếu có cái nào được thì lấy cái đó, 2 cái đều được thì lấy min.
* Lưu ý: Khi CC chỉ có 1 vertex thì 1 TH duy nhất là phải color nó = 1 (guard here)
Code:
Comments
Post a Comment