1 năm, 4 tháng trước

Xin mọi người cho mình ý tưởng giải bài này được không ạ! Có phải ứng dụng Luồng không?! Nếu ứng dụng thì ta xây dựng đồ thị dạng luồng như thế nào? Mọi người giúp mình với! Xin chân thành cảm ơn!

1 năm, 4 tháng trước

Đây là hướng làm của mình:

Để tìm được 1 nghiệm thỏa mãn, ta có thể quy về bài toán tìm 1 lát cắt s-t của đồ thị mà có kích thước < G (bạn có thể tìm hiểu thêm về lát cắt và lát cắt cực tiểu) -> có thể tìm bằng luồng

Với độ dài tối đa cho trước bất kì, chỉ có một số vị trí có thể đặt lính -> chỉ có một số cạnh có thể thuộc tập hợp cắt.

Như vậy với mỗi độ dài tối đa cho trước, bạn có thể xây đồ thị sao cho lát cắt cực tiểu tìm được trên đồ thị này chỉ có thể cắt các cạnh có thể đặt lính.

Mình chỉ gợi ý đến thế thôi